Back to Search Start Over

Algorithms for Pedigree Comparison.

Authors :
Chen, Zhi-Zhong
Feng, Qilong
Shen, Chao
Wang, Jianxin
Wang, Lusheng
Source :
IEEE/ACM Transactions on Computational Biology & Bioinformatics; Mar/Apr2018, Vol. 15 Issue 2, p422-431, 10p
Publication Year :
2018

Abstract

Reconstruction of ancestral relationships among genera, species, and populations is a core task in evolutionary biology. At the population level, pedigrees have been commonly used. Reconstruction of pedigree is required in practice due to legal or medical reasons. Pedigrees are very important to geneticists for inferring haplotype segments, recombination, and allele sharing status with which disease loci can be identified. Evaluating reconstruction methods requires comparing the inferred pedigree and the known pedigrees. Moreover, comparison of pedigrees is required in studying relationships among crops such as maize, wheat and barley, etc. In this paper, we discuss three models for comparison of pedigrees, the maximum pedigree isomorphism problem, the maximum paternal-path-preserved mapping problem, and the minimum edge-cutting mapping problem. For the maximum pedigree isomorphism problem, we prove that the problem is NP-hard and give a fixed-parameter algorithm for the problem. For the maximum paternal-path-preserved mapping problem, we give a dynamic-programming algorithm to find the mapping that preserves the maximum number of paternal paths between the two input pedigrees. For the minimum edge-cutting mapping problem, we prove that the problem is NP-hard and give a fixed-parameter algorithm with running time O(n(1+\sqrt2)^k)<alternatives> <inline-graphic xlink:href="wang-ieq1-2550434.gif"/></alternatives>, where $n$<alternatives><inline-graphic xlink:href="wang-ieq2-2550434.gif"/> </alternatives> is the number of vertices in the two input pedigrees and $k$<alternatives><inline-graphic xlink:href="wang-ieq3-2550434.gif"/> </alternatives> is the number of edges to be cut. This algorithm is useful in practice when comparing two similar pedigrees. [ABSTRACT FROM PUBLISHER]

Details

Language :
English
ISSN :
15455963
Volume :
15
Issue :
2
Database :
Complementary Index
Journal :
IEEE/ACM Transactions on Computational Biology & Bioinformatics
Publication Type :
Academic Journal
Accession number :
128843333
Full Text :
https://doi.org/10.1109/TCBB.2016.2550434