title: Constructing near-perfect phylogenies with multiple homoplasy events.
abstract: 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.
authors.affiliation: School of EECS, University of Central Florida, Orlando, FL 32816-2362, USA. rvijaya@cs.ucf.edu
authors.forename: Ravi Vijaya
authors.initials: RV
authors.lastname: Satya
authors.forename: Amar
authors.initials: A
authors.lastname: Mukherjee
authors.forename: Gabriela
authors.initials: G
authors.lastname: Alexe
authors.forename: Laxmi
authors.initials: L
authors.lastname: Parida
authors.forename: Gyan
authors.initials: G
authors.lastname: Bhanot
mesh_terms: 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*