Constructing near-perfect phylogenies with multiple homoplasy events.
BACKGROUND
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(m(q+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.


BACKGROUND
The implementation of our algorithm for the H1-NPPH problem is available upon request.
Satya
Ravi Vijaya
RV
School of EECS, University of Central Florida, Orlando, FL 32816-2362, USA. rvijaya@cs.ucf.edu
Mukherjee
Amar
A
Alexe
Gabriela
G
Parida
Laxmi
L
Bhanot
Gyan
G
D000465:Algorithms; D001483:Base Sequence; D005075:Biological Evolution; D002874:Chromosome Mapping / Q000379:methods*; D004252:DNA Mutational Analysis / Q000379:methods*; D015894:Genome, Human / Q000235:genetics; D006239:Haplotypes / Q000235:genetics; D006801:Humans; D015810:Linkage Disequilibrium / Q000235:genetics*; D008969:Molecular Sequence Data; D010802:Phylogeny; D020641:Polymorphism, Single Nucleotide / Q000235:genetics*; D016415:Sequence Alignment / Q000379:methods*; D017422:Sequence Analysis, DNA / Q000379:methods*