Isomorphism and similarity for 2-generation pedigrees

BMC Bioinformatics

Proceedings

Binhai Zhu¹  Weitian Tong²  Guohui Lin²  Haitao Jiang³  Daming Zhu³ 

[1] Department of Computer Science, Montana State University, 59717, Bozeman, MT, USA;Department of Computing Science, University of Alberta, T2G 2E6, Edmonton, Alberta, Germany;School of Computer Science and Technology, Shandong University, 1500 Shunhua Road, 250101, Jinan, Shandong, China;

关键词: pedigree similarity;    graph isomorphism;    NP-complete;    FPT algorithms;   

DOI  :  10.1186/1471-2105-16-S5-S7

来源: Springer

【 摘 要 】

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.

【 授权许可】

Unknown   
© Jiang et al.; licensee BioMed Central Ltd. 2015. This article is published under license to BioMed Central Ltd. 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.