Constructing Near-Perfect Phylogenies with multiple homoplasy events

    Authors

    R. V. Satya; A. Mukherjee; G. Alexe; L. Parida;G. Bhanot

    Comments

    Authors: contact us about adding a copy of your work at STARS@ucf.edu

    Abbreviated Journal Title

    Bioinformatics

    Keywords

    SAMPLES; Biochemical Research Methods; Biotechnology & Applied Microbiology; Computer Science, Interdisciplinary Applications; Mathematical &; Computational Biology; Statistics & Probability

    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(m(2)(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( n 4) 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 accuracyof our algorithm for theH1-NPPHproblemiscomparableto that of the existing methods, while being orders of magnitude faster. Availability: The implementation of our algorithm for the H1-NPPH problem is available upon request.

    Journal Title

    Bioinformatics

    Volume

    22

    Issue/Number

    14

    Publication Date

    1-1-2006

    Document Type

    Article; Proceedings Paper

    Language

    English

    First Page

    E514

    Last Page

    E522

    WOS Identifier

    WOS:000250005000063

    ISSN

    1367-4803

    Share

    COinS