Title

Constructing Near-Perfect Phylogenies With Multiple Homoplasy Events

Abstract

Motivation: We explore the problem of constructing near-perfect phylogenies on bi-allelic haplotypes, where the deviation from perfect phylogeny is entirely due to homoplasy events. We present polynomial-time algorithms for restricted versions of the problem. We show that these algorithms can be extended to genotype data, in which case the problem is called the near-perfect phylogeny haplotyping (NPPH) problem. We present a near-optimal algorithm for the H1-NPPH problem, which is to determine if a given set of genotypes admit a phylogeny with a single homoplasy event. The time-complexity of our algorithm for the H1-NPPH problem is O(m2(n + m)), where n is the number of genotypes and m is the number of SNP sites. This is a significant improvement over the earlier O(n4) algorithm. We also introduce generalized versions of the problem. The H(1, q)-NPPH problem is to determine if a given set of genotypes admit a phylogeny with q homoplasy events, so that all the homoplasy events occur in a single site. We present an O (mq+1(n + m)) algorithm for the H(1, q)-NPPH problem. Results: We present results on simulated data, which demonstrate that the accuracy of our algorithm for the H1-NPPH problem is comparable to that of the existing methods, while being orders of magnitude faster. © 2006 Oxford University Press.

Publication Date

7-15-2006

Publication Title

Bioinformatics

Volume

22

Issue

14

Number of Pages

-

Document Type

Article; Proceedings Paper

Personal Identifier

scopus

DOI Link

https://doi.org/10.1093/bioinformatics/btl262

Socpus ID

33747881294 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/33747881294

This document is currently not available here.

Share

COinS