article

The Undirected Incomplete Perfect Phylogeny Problem

Authors:

Ravi Vijaya Satya,

Amar MukherjeeAuthors Info & Claims

IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), Volume 5, Issue 4

Pages 618 - 629

https://doi.org/10.1109/TCBB.2007.70218

Published: 01 October 2008 Publication History

Publisher Site Get Access

Abstract

The incomplete perfect phylogeny (IPP) problem and the incomplete perfect phylogeny haplotyping (IPPH) problem deal with constructing a phylogeny for a given set of haplotypes or genotypes with missing entries. The earlier approaches for both of these problems dealt with restricted versions of the problems, where the root is either available or can be trivially re-constructed from the data, or certain assumptions were made about the data. In this paper, we deal with the unrestricted versions of the problems, where the root of the phylogeny is neither available nor trivially recoverable from the data. Both IPP and IPPH problems have previously been proven to be NPcomplete. Here, we present efficient enumerative algorithms that can handle practical instances of the problem. Empirical analysis on simulated data shows that the algorithms perform very well both in terms of speed and in terms accuracy of the recovered data.

References

[1]

R. Agarwala and D. Fernandez-Baca, "A Polynomial-Time Algorithm for the Perfect Phylogeny Problem When the Number of Character States Is Fixed," SIAM J. Computing, vol. 23, pp. 1216- 1224, 1994.

Digital Library

[2]

HapMapConsortium, "The International Hapmap Project," Nature , vol. 426, pp. 789-796, Dec. 2003.

[3]

A.G. Clark, "Inference of Haplotypes from PCR-Amplified Samples of Diploid Populations," Molecular Biology and Evolution, vol. 7, pp. 111-122, 1990.

[4]

D. Gusfield, "Haplotyping as Perfect Phylogeny: Conceptual Framework and Efficient Solutions," Proc. Ann. Int'l Conf. Research in Computational Molecular Biology (RECOMB), 2002.

Digital Library

[5]

Y. Liu and C.-Q. Zhang, "A Linear Solution for Haplotype Perfect Phylogeny Problem," Proc. Int'l Conf. Bioinformatics and Its Applications (ICBA), 2004.

[6]

R. Vijaya Satya and A. Mukherjee, "An Efficient Algorithm for Perfect Phylogeny Haplotyping," Proc. IEEE CS Computational Systems Bioinformatics Conf. (CSB '05), pp. 103-110, Aug. 2005.

Digital Library

[7]

Z. Ding, V. Filkov, and D. Gusfield, "A Linear Time Algorithm for the Perfect Phylogeny Haplotyping (PPH) Problem," Proc. Ann. Int'l Conf. Research in Computational Molecular Biology (RECOMB '05), pp. 585-600, 2005.

Digital Library

[8]

Z. Ding, V. Filkov, and D. Gusfield, "A Linear Time Algorithm for the Perfect Phylogeny Haplotyping (PPH) Problem," J. Computational Biology, vol. 13, no. 2, pp. 522-553, 2006.

[9]

R. Vijaya Satya and A. Mukherjee, "An Optimal Algorithm for Perfect Phylogeny Haplotyping," J. Computational Biology, vol. 13, no. 4, pp. 897-928, 2006.

[10]

M. Steel, "The Complexity of Reconstructing Trees from Qualitative Characters and Subtrees," J. Classification, vol. 9, pp. 91-116, 1992.

[11]

I. Peer, T. Pupko, R. Shamir, and R. Sharan, "Incomplete Directed Perfect Phylogeny," SIAM J. Computing, vol. 33, no. 3, pp. 590-607, 2004.

Digital Library

[12]

G. Kimmel and R. Shamir, "The Incomplete Perfect Phylogeny Problem," J. Bioinformatics and Computational Biology, vol. 3, no. 2, pp. 1-25, 2005.

[13]

E. Halperin and R. Karp, "Perfect Phylogeny and Haplotype Assignment," Proc. Ann. Int'l Conf. Research in Computational Molecular Biology (RECOMB), 2004.

Digital Library

[14]

R. Vijaya Satya and A. Mukherjee, The Undirected Incomplete Perfect Phylogeny Problem, Technical Report CS-TR-05-11, School of Computer Science, Univ. of Central Florida, Dec. 2005.

[15]

J. Gramm, T. Nierhoff, R. Sharan, and T. Tantau, "Haplotyping with Missing Data via Perfect Path Phylogenies," Proc. Second RECOMB Satellite Workshop Computational Methods for SNPs and Haplotypes, pp. 35-46, 2004.

[16]

V. Bafna, D. Gusfield, G. Lancia, and S. Yooseph, "Haplotyping as Perfect Phylogeny: A Direct Approach," J. Computational Biology, vol. 10, nos. 3-4, pp. 323-340, 2003.

[17]

R. Hudson, "Generating Samples under the Wright-Fisher Neutral Model of Genetic Variation," Bioinformatics, vol. 18, pp. 337-338, 2002.

Cited By

Bernardini GBonizzoni PGawrychowski P(2021)Incomplete Directed Perfect Phylogeny in Linear TimeAlgorithms and Data Structures10.1007/978-3-030-83508-8_13(172-185)Online publication date: 9-Aug-2021
https://dl.acm.org/doi/10.1007/978-3-030-83508-8_13
Kirkpatrick BStevens K(2014)Perfect phylogeny problems with missing valuesIEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB)10.1109/TCBB.2014.231600511:5(928-941)Online publication date: 1-Sep-2014
https://dl.acm.org/doi/10.1109/TCBB.2014.2316005
Stevens KKirkpatrick B(2011)Efficiently solvable perfect phylogeny problems on binary and k-state data with missing valuesProceedings of the 11th international conference on Algorithms in bioinformatics10.5555/2039945.2039969(282-297)Online publication date: 5-Sep-2011
https://dl.acm.org/doi/10.5555/2039945.2039969
Show More Cited By

Index Terms

The Undirected Incomplete Perfect Phylogeny Problem

Recommendations

Computational Problems in Perfect Phylogeny Haplotyping: Typing without Calling the Allele

A haplotype is an m-long binary vector. The xor-genotype of two haplotypes is the m-vector of their coordinate-wise xor. We study the following problem: Given a set of xor-genotypes, reconstruct their haplotypes so that the set of resulting haplotypes ...
Haplotyping as perfect phylogeny: conceptual framework and efficient solutions
RECOMB '02: Proceedings of the sixth annual international conference on Computational biology

The next high-priority phase of human genomics will involve the development of a full Haplotype Map of the human genome [12]. It will be used in large-scale screens of populations to associate specific haplotypes with specific complex genetic-influenced ...
Phylogeny- and parsimony-based haplotype inference with constraints

Haplotyping, also known as haplotype phase prediction, is the problem of predicting likely haplotypes based on genotype data. One fast computational haplotyping method is based on an evolutionary model where a perfect phylogenetic tree is sought that ...

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Computational Biology and Bioinformatics

IEEE/ACM Transactions on Computational Biology and Bioinformatics Volume 5, Issue 4

October 2008

158 pages

ISSN:1545-5963

Issue’s Table of Contents

Publisher

IEEE Computer Society Press

Washington, DC, United States

Publication History

Published: 01 October 2008

Published in TCBB Volume 5, Issue 4

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
112
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Bernardini GBonizzoni PGawrychowski P(2021)Incomplete Directed Perfect Phylogeny in Linear TimeAlgorithms and Data Structures10.1007/978-3-030-83508-8_13(172-185)Online publication date: 9-Aug-2021
https://dl.acm.org/doi/10.1007/978-3-030-83508-8_13
Kirkpatrick BStevens K(2014)Perfect phylogeny problems with missing valuesIEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB)10.1109/TCBB.2014.231600511:5(928-941)Online publication date: 1-Sep-2014
https://dl.acm.org/doi/10.1109/TCBB.2014.2316005
Stevens KKirkpatrick B(2011)Efficiently solvable perfect phylogeny problems on binary and k-state data with missing valuesProceedings of the 11th international conference on Algorithms in bioinformatics10.5555/2039945.2039969(282-297)Online publication date: 5-Sep-2011
https://dl.acm.org/doi/10.5555/2039945.2039969
Stevens KGusfield D(2010)Reducing multi-state to binary perfect phylogeny with applications to missing, removable, inserted, and deleted dataProceedings of the 10th international conference on Algorithms in bioinformatics10.5555/1885783.1885812(274-287)Online publication date: 6-Sep-2010
https://dl.acm.org/doi/10.5555/1885783.1885812
Elberfeld MSchnoor ITantau T(2009)Influence of Tree Topology Restrictions on the Complexity of Haplotyping with Missing DataProceedings of the 6th Annual Conference on Theory and Applications of Models of Computation10.1007/978-3-642-02017-9_23(201-210)Online publication date: 12-May-2009
https://dl.acm.org/doi/10.1007/978-3-642-02017-9_23
Elberfeld MTantau T(2008)Computational Complexity of Perfect-Phylogeny-Related Haplotyping ProblemsProceedings of the 33rd international symposium on Mathematical Foundations of Computer Science10.1007/978-3-540-85238-4_24(299-310)Online publication date: 25-Aug-2008
https://dl.acm.org/doi/10.1007/978-3-540-85238-4_24

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents