| The Multi-State Perfect Phylogeny Problem with missing and removable data: solutions via integer-programming and chordal graph theory. | |
| | |
MedLine Citation:
|
PMID: 20377452 Owner: NLM Status: MEDLINE |
Abstract/OtherAbstract:
|
The Multi-State Perfect Phylogeny Problem is an extension of the Binary Perfect Phylogeny Problem, allowing characters to take on more than two states. In this article, we consider three problems that extend the utility of the multi-state perfect phylogeny model: (1) the Missing Data (MD) Problem, where some entries in the input are missing and the question is whether (bounded) values for the missing data can be imputed so that the resulting data has a multi-state perfect phylogeny; (2) the Character-Removal (CR) Problem, where we want to minimize the number of characters to remove from the data so that the resulting data has a multi-state perfect phylogeny; and (3) the Missing-Data Character-Removal (MDCR) Problem, where the input has missing data and we want to impute values for the missing data to minimize the solution to the resulting Character-Removal Problem. We discuss Integer Linear Programming (ILP) solutions to these problems for the special case of three, four, and five permitted states per character, and we report on extensive empirical testing of these solutions. Then we develop a general theory to solve the MD problem for an arbitrary number of permitted states, using chordal graph theory and results on minimal triangulation of non-chordal graphs. This establishes new necessary and sufficient conditions for the existence of a perfect phylogeny with (or without) missing data. We implement the general theory using integer linear programming, although other optimization methods are possible. We extensively explore the empirical behavior of the general solution, showing that the methods are very practical for data of size and complexity that is characteristic of many current applications in phylogenetics. Some of the empirical results for the MD problem with an arbitrary number of permitted states are very surprising, suggesting the existence of additional combinatorial structure in multi-state perfect phylogenies. Finally, we note some relationships between our chordal-graph approach to the multi-state perfect phylogeny, without missing data, and prior methods. |
| | |
Authors:
|
Dan Gusfield |
Publication Detail:
|
Type: Journal Article; Research Support, U.S. Gov't, Non-P.H.S. |
Journal Detail:
|
Title: Journal of computational biology : a journal of computational molecular cell biology Volume: 17 ISSN: 1557-8666 ISO Abbreviation: J. Comput. Biol. Publication Date: 2010 Mar |
Date Detail:
|
Created Date: 2010-04-09 Completed Date: 2010-07-01 Revised Date: - |
Medline Journal Info:
|
Nlm Unique ID: 9433358 Medline TA: J Comput Biol Country: United States |
Other Details:
|
Languages: eng Pagination: 383-99 Citation Subset: IM |
Affiliation:
|
Department of Computer Science, University of California, Davis, Davis, California 95616, USA. gusfield@cs.ucdavis.edu |
Export Citation:
|
APA/MLA Format Download EndNote Download BibTex |
| MeSH Terms | |
Descriptor/Qualifier:
|
Algorithms Animals Computational Biology Phylogeny* Programming, Linear* Statistics as Topic* Time Factors |
From MEDLINE®/PubMed®, a database of the U.S. National Library of Medicine
Previous Document: Optimizing PCR assays for DNA-based cancer diagnostics.
Next Document: COE: a general approach for efficient genome-wide two-locus epistasis test in disease association st...