Skip Navigation



Bioinformatics Advance Access published online on August 23, 2006
Bioinformatics, doi:10.1093/bioinformatics/btl452
This Article
Right arrow Advance Access manuscript (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 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 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
Received July 3, 2006
Revised August 16, 2006
Accepted August 16, 2006

Article

Maximum likelihood of phylogenetic networks

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

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

* To whom correspondence should be addressed.
Tamir Tuller, E-mail: tamirtul{at}post.tau.ac.il


  Abstract

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 in human health, developing accurate and efficient methods for detecting and reconstructing HGT is imperative.

Results: In this paper 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.

Associate Editor: Keith A Crandall
Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?


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, September 16, 2009; (2009) syp055v1.
[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.