Title |
Isomorphism and similarity for 2-generation pedigrees
|
---|---|
Published in |
BMC Bioinformatics, March 2015
|
DOI | 10.1186/1471-2105-16-s5-s7 |
Pubmed ID | |
Authors |
Haitao Jiang, Guohui Lin, Weitian Tong, Daming Zhu, Binhai Zhu |
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. |
X Demographics
Geographical breakdown
Country | Count | As % |
---|---|---|
Unknown | 1 | 100% |
Demographic breakdown
Type | Count | As % |
---|---|---|
Members of the public | 1 | 100% |
Mendeley readers
Geographical breakdown
Country | Count | As % |
---|---|---|
Unknown | 7 | 100% |
Demographic breakdown
Readers by professional status | Count | As % |
---|---|---|
Professor | 2 | 29% |
Researcher | 2 | 29% |
Student > Ph. D. Student | 1 | 14% |
Lecturer | 1 | 14% |
Unknown | 1 | 14% |
Readers by discipline | Count | As % |
---|---|---|
Computer Science | 4 | 57% |
Biochemistry, Genetics and Molecular Biology | 2 | 29% |
Agricultural and Biological Sciences | 1 | 14% |