Title

The Undirected Incomplete Perfect Phylogeny Problem

Keywords

Haplotype inference; Incomplete perfect phylogeny; Perfect phylogeny; Phylogenetics

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 reconstructed 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 NP-complete. 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. © 2008 IEEE.

Publication Date

10-1-2008

Publication Title

IEEE/ACM Transactions on Computational Biology and Bioinformatics

Volume

5

Issue

4

Number of Pages

618-629

Document Type

Article; Proceedings Paper

Personal Identifier

scopus

DOI Link

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

Socpus ID

55949095815 (Scopus)

Source API URL

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

This document is currently not available here.

Share

COinS