标题:Isomorphism and similarity for 2-generation pedigrees
作者:Jiang, Haitao; Lin, Guohui; Tong, Weitian; Zhu, Daming; Zhu, Binhai
通讯作者:Zhu, Binhai
作者机构:[Jiang, Haitao; Zhu, Daming] Shandong Univ, Sch Comp Sci & Technol, Jinan 250101, Shandong, Peoples R China.; [Lin, Guohui; Tong, Weitian] Univ Albe 更多
会议名称:10th International Symposium on Bioinformatics Research and Applications (ISBRA) - Bioinformatics
会议日期:JUN 28-30, 2014
来源:BMC BIOINFORMATICS
出版年:2015
卷:16
期:5
DOI:10.1186/1471-2105-16-S5-S7
摘要: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.
收录类别:CPCI-S;EI;SCOPUS;SCIE
WOS核心被引频次:1
Scopus被引频次:1
资源类型:会议论文;期刊论文
原文链接:https://www.scopus.com/inward/record.uri?eid=2-s2.0-84961551517&doi=10.1186%2f1471-2105-16-S5-S7&partnerID=40&md5=de69b95e528ba7c9c58bf0b113084e7c
TOP