Document Detail


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.