Document Detail

Constructing a minimum phylogenetic network from a dense triplet set.
MedLine Citation:
PMID:  22849368     Owner:  NLM     Status:  MEDLINE    
For a given set L of species and a set T of triplets on L, we seek to construct a phylogenetic network which is consistent with T i.e. which represents all triplets of T. The level of a network is defined as the maximum number of hybrid vertices in its biconnected components. When T 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 T, if there is any, in time O(T(k+1)n([4k/3]+1)).
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:  1757-6334     ISO Abbreviation:  J Bioinform Comput Biol     Publication Date:  2012 Oct 
Date Detail:
Created Date:  2012-08-01     Completed Date:  2012-12-04     Revised Date:  2014-10-13    
Medline Journal Info:
Nlm Unique ID:  101187344     Medline TA:  J Bioinform Comput Biol     Country:  England    
Other Details:
Languages:  eng     Pagination:  1250013     Citation Subset:  IM    
Export Citation:
APA/MLA Format     Download EndNote     Download BibTex
MeSH Terms
Computational Biology / methods*
Evolution, Molecular
Gene Regulatory Networks*

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.