Skip Navigation


Bioinformatics Advance Access originally published online on August 23, 2006
Bioinformatics 2006 22(21):2604-2611; doi:10.1093/bioinformatics/btl452
This Article
Right arrow Full Text Freely available
Right arrow FREE Full Text (Print PDF) Freely available
Right arrow All Versions of this Article:
22/21/2604    most recent
btl452v1
Right arrow Comments: Submit a response
Right arrow Alert me when this article is cited
Right arrow Alert me when Comments are posted
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Related articles in Bioinformatics
Right arrow Similar articles in this journal
Right arrow Similar articles in PubMed
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrow Search for citing articles in:
ISI Web of Science (7)
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Jin, G.
Right arrow Articles by Tuller, T.
Right arrow Search for Related Content
PubMed
Right arrow PubMed Citation
Right arrow Articles by Jin, G.
Right arrow Articles by Tuller, T.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

© The Author 2006. Published by Oxford University Press. All rights reserved. For Permissions, please email: journals.permissions@oxfordjournals.org

Maximum likelihood of phylogenetic networks

Guohua Jin 1, Luay Nakhleh 1, Sagi Snir 2 and Tamir Tuller 3,*

1 Department of Computer Science, Rice University Houston, TX, USA
2 Department of Mathematics, University of California Berkeley, CA, USA
3 School of Computer Science, Tel-Aviv University Israel

*To whom correspondence should be addressed.

Motivation: Horizontal gene transfer (HGT) is believed to be ubiquitous among bacteria, and plays a major role in their genome diversification as well as their ability to develop resistance to antibiotics. In light of its evolutionary significance and implications for human health, developing accurate and efficient methods for detecting and reconstructing HGT is imperative.

Results: In this article we provide a new HGT-oriented likelihood framework for many problems that involve phylogeny-based HGT detection and reconstruction. Beside the formulation of various likelihood criteria, we show that most of these problems are NP-hard, and offer heuristics for efficient and accurate reconstruction of HGT under these criteria. We implemented our heuristics and used them to analyze biological as well as synthetic data. In both cases, our criteria and heuristics exhibited very good performance with respect to identifying the correct number of HGT events as well as inferring their correct location on the species tree.

Availability: Implementation of the criteria as well as heuristics and hardness proofs are available from the authors upon request. Hardness proofs can also be downloaded at http://www.cs.tau.ac.il/~tamirtul/MLNET/Supp-ML.pdf

Contact: tamirtul{at}post.tau.ac.il

Supplementary information: Supplementary data are available at Bioinformatics online.

Received on July 3, 2006; revised on August 16, 2006; accepted on August 16, 2006

Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?

Related articles in Bioinformatics:

Maximum likelihood of phylogenetic networks
Guohua Jin, Luay Nakhleh, Sagi Snir, and Tamir Tuller
Bioinformatics 2007 23: 1046-1047. [Extract] [FREE Full Text]  



This article has been cited by other articles:


Home page
 Syst BiolHome page
E. W. Bloomquist and M. A. Suchard
Unifying Vertical and Nonvertical Evolution: A Stochastic ARG-based Framework
Syst Biol, November 9, 2009; (2009) syp076v1.
[Abstract] [Full Text] [PDF]

Home page
 Syst BiolHome page
L. S. Kubatko
Identifying Hybridization Events in the Presence of Coalescence via Model Selection
Syst Biol, October 1, 2009; 58(5): 478 - 488.
[Abstract] [Full Text] [PDF]

Home page
 BioinformaticsHome page
G. Cardona, M. Llabres, F. Rossello, and G. Valiente
A distance metric for a class of tree-sibling phylogenetic networks
Bioinformatics, July 1, 2008; 24(13): 1481 - 1488.
[Abstract] [Full Text] [PDF]

Home page
 Mol Biol EvolHome page
S. Munshaw and T. B. Kepler
An Information-Theoretic Method for the Treatment of Plural Ancestry in Phylogenetics
Mol. Biol. Evol., June 1, 2008; 25(6): 1199 - 1208.
[Abstract] [Full Text] [PDF]

Home page
 BioinformaticsHome page
H. Birin, Z. Gal-Or, I. Elias, and T. Tuller
Inferring horizontal transfers in the presence of rearrangements by the minimum evolution criterion
Bioinformatics, March 15, 2008; 24(6): 826 - 832.
[Abstract] [Full Text] [PDF]

Home page
 Syst BiolHome page
N. Galtier
A Model of Horizontal Gene Transfer and the Bacterial Phylogeny Problem
Syst Biol, August 1, 2007; 56(4): 633 - 642.
[Abstract] [Full Text] [PDF]

Home page
 Proc. Natl. Acad. Sci. USAHome page
W. F. Doolittle and E. Bapteste
Inaugural Article: Pattern pluralism and the Tree of Life hypothesis
PNAS, February 13, 2007; 104(7): 2043 - 2049.
[Abstract] [Full Text] [PDF]

Home page
 Mol Biol EvolHome page
G. Jin, L. Nakhleh, S. Snir, and T. Tuller
Inferring Phylogenetic Networks by the Maximum Parsimony Criterion: A Case Study
Mol. Biol. Evol., January 1, 2007; 24(1): 324 - 337.
[Abstract] [Full Text] [PDF]


Disclaimer: Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.