| Constructing a minimum phylogenetic network from a dense triplet set. | |
| | |
MedLine Citation:
|
PMID: 22849368 Owner: NLM Status: In-Data-Review |
Abstract/OtherAbstract:
|
For a given set [Formula: see text] of species and a set [Formula: see text] of triplets on [Formula: see text], we seek to construct a phylogenetic network which is consistent with [Formula: see text] i.e. which represents all triplets of [Formula: see text]. The level of a network is defined as the maximum number of hybrid vertices in its biconnected components. When [Formula: see text] is dense, there exist polynomial time algorithms to construct level-0,1 and 2 networks (Aho et al., 1981; Jansson, Nguyen and Sung, 2006; Jansson and Sung, 2006; Iersel et al., 2009). For higher levels, partial answers were obtained in the paper by Iersel and Kelk (2008), with a polynomial time algorithm for simple networks. In this paper, we detail the first complete answer for the general case, solving a problem proposed in Jansson and Sung (2006) and Iersel et al. (2009). For any k fixed, it is possible to construct a level-k network having the minimum number of hybrid vertices and consistent with [Formula: see text], if there is any, in time [Formula: see text]. |
| | |
Authors:
|
Michel Habib; Thu-Hien To |
Related Documents
:
|
22029428 - An efficient simulator of 454 data using configurable statistical models. 22168108 - Simulated seasonal variations in wet acid depositions over east asia. 22234858 - Gene genealogies within a fixed pedigree, and the robustness of kingman's coalescent. 22116738 - Kernel smoothing density estimation when group membership is subject to missing. 16929748 - Meteorological variation effect on aerobiology--new tools on pollen forecasting. 8995048 - The perception of spatial layout in real and virtual worlds. |
Publication Detail:
|
Type: Journal Article |
Journal Detail:
|
Title: Journal of bioinformatics and computational biology Volume: 10 ISSN: 0219-7200 ISO Abbreviation: J Bioinform Comput Biol Publication Date: 2012 Oct |
Date Detail:
|
Created Date: 2012-08-01 Completed Date: - Revised Date: - |
Medline Journal Info:
|
Nlm Unique ID: 101187344 Medline TA: J Bioinform Comput Biol Country: England |
Other Details:
|
Languages: eng Pagination: 1250013 Citation Subset: IM |
Affiliation:
|
Université Paris Diderot - Paris 7, LIAFA, Case 7014, 75205 Paris Cedex 13, France. |
Export Citation:
|
APA/MLA Format Download EndNote Download BibTex |
| MeSH Terms | |
Descriptor/Qualifier:
|
|
From MEDLINE®/PubMed®, a database of the U.S. National Library of Medicine
Previous Document: Inferring the regulatory interaction models of transcription factors in transcriptional regulatory n...
Next Document: Metagenomic taxonomic classification using extreme learning machines.