Cargando…

Isomorphism and similarity for 2-generation pedigrees

We consider the emerging problem of comparing the similarity between (unlabeled) pedigrees. More specifically, we focus on the simplest pedigrees, namely, the 2-generation pedigrees. We show that the isomorphism testing for two 2-generation pedigrees is GI-hard. If the 2-generation pedigrees are mon...

Descripción completa

Detalles Bibliográficos
Autores principales: Jiang, Haitao, Lin, Guohui, Tong, Weitian, Zhu, Daming, Zhu, Binhai
Formato: Online Artículo Texto
Lenguaje:English
Publicado: BioMed Central 2015
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4402698/
https://www.ncbi.nlm.nih.gov/pubmed/25860335
http://dx.doi.org/10.1186/1471-2105-16-S5-S7
_version_ 1782367291919302656
author Jiang, Haitao
Lin, Guohui
Tong, Weitian
Zhu, Daming
Zhu, Binhai
author_facet Jiang, Haitao
Lin, Guohui
Tong, Weitian
Zhu, Daming
Zhu, Binhai
author_sort Jiang, Haitao
collection PubMed
description We consider the emerging problem of comparing the similarity between (unlabeled) pedigrees. More specifically, we focus on the simplest pedigrees, namely, the 2-generation pedigrees. We show that the isomorphism testing for two 2-generation pedigrees is GI-hard. If the 2-generation pedigrees are monogamous (i.e., each individual at level-1 can mate with exactly one partner) then the isomorphism testing problem can be solved in polynomial time. We then consider the problem by relaxing it into an NP-complete decomposition problem which can be formulated as the Minimum Common Integer Pair Partition (MCIPP) problem, which we show to be FPT by exploiting a property of the optimal solution. While there is still some difficulty to overcome, this lays down a solid foundation for this research.
format Online
Article
Text
id pubmed-4402698
institution National Center for Biotechnology Information
language English
publishDate 2015
publisher BioMed Central
record_format MEDLINE/PubMed
spelling pubmed-44026982015-04-29 Isomorphism and similarity for 2-generation pedigrees Jiang, Haitao Lin, Guohui Tong, Weitian Zhu, Daming Zhu, Binhai BMC Bioinformatics Proceedings We consider the emerging problem of comparing the similarity between (unlabeled) pedigrees. More specifically, we focus on the simplest pedigrees, namely, the 2-generation pedigrees. We show that the isomorphism testing for two 2-generation pedigrees is GI-hard. If the 2-generation pedigrees are monogamous (i.e., each individual at level-1 can mate with exactly one partner) then the isomorphism testing problem can be solved in polynomial time. We then consider the problem by relaxing it into an NP-complete decomposition problem which can be formulated as the Minimum Common Integer Pair Partition (MCIPP) problem, which we show to be FPT by exploiting a property of the optimal solution. While there is still some difficulty to overcome, this lays down a solid foundation for this research. BioMed Central 2015-03-18 /pmc/articles/PMC4402698/ /pubmed/25860335 http://dx.doi.org/10.1186/1471-2105-16-S5-S7 Text en Copyright © 2015 Jiang et al.; licensee BioMed Central Ltd. http://creativecommons.org/licenses/by/4.0 This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. The Creative Commons Public Domain Dedication waiver (http://creativecommons.org/publicdomain/zero/1.0/) applies to the data made available in this article, unless otherwise stated.
spellingShingle Proceedings
Jiang, Haitao
Lin, Guohui
Tong, Weitian
Zhu, Daming
Zhu, Binhai
Isomorphism and similarity for 2-generation pedigrees
title Isomorphism and similarity for 2-generation pedigrees
title_full Isomorphism and similarity for 2-generation pedigrees
title_fullStr Isomorphism and similarity for 2-generation pedigrees
title_full_unstemmed Isomorphism and similarity for 2-generation pedigrees
title_short Isomorphism and similarity for 2-generation pedigrees
title_sort isomorphism and similarity for 2-generation pedigrees
topic Proceedings
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4402698/
https://www.ncbi.nlm.nih.gov/pubmed/25860335
http://dx.doi.org/10.1186/1471-2105-16-S5-S7
work_keys_str_mv AT jianghaitao isomorphismandsimilarityfor2generationpedigrees
AT linguohui isomorphismandsimilarityfor2generationpedigrees
AT tongweitian isomorphismandsimilarityfor2generationpedigrees
AT zhudaming isomorphismandsimilarityfor2generationpedigrees
AT zhubinhai isomorphismandsimilarityfor2generationpedigrees