Isomorphism and similarity for 2-generation pedigrees. Issue 5 (December 2015)

• Record Type: Journal Article
• Authors: Jiang, Haitao; Lin, Guohui; Tong, Weitian; Zhu, Daming; Zhu, Binhai
• Is Part Of: BMC bioinformatics. Volume 16:Issue 5(2015)
• Page Start: 1
• Page End: 8
• Publication Date: 2015-12
• Subjects: pedigree similarity -- graph isomorphism -- NP-complete -- FPT algorithms; Bioinformatics -- Periodicals; Computational biology -- Periodicals; 570.285
• DOI: 10.1186/1471-2105-16-S5-S7
• Languages: English
• ISSNs: 1471-2105

Abstract

Abstract 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.