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 :
21571338 - Effectiveness of procedural simulation in urology: a systematic review.
21712588 - Modeling sediment and nitrogen export from a rural watershed in eastern canada using th...
17225808 - Model-based phase velocity and attenuation estimation in wideband ultrasonic measuremen...
3268268 - Interviewing older adults: validity of self-reports of satisfaction.
11604868 - Haptic reproduction and interactive visualization of a beating heart based on cardiac m...
18249758 - A novel normalization technique for unsupervised learning in ann.
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.