Skip Navigation


Bioinformatics Advance Access first published online on January 18, 2008
This version published online on February 4, 2008
Bioinformatics, doi:10.1093/bioinformatics/btn024
This Article
Right arrow Advance Access manuscript (PDF)
Right arrow Supplementary Data
Right arrow All Versions of this Article:
24/6/826    most recent
btn024v2
btn024v1
Right arrow Alert me when this article is cited
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 Birin, H.
Right arrow Articles by Tuller, T.
Right arrow Search for Related Content
PubMed
Right arrow PubMed Citation
Right arrow Articles by Birin, H.
Right arrow Articles by Tuller, T.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

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

Inferring Horizontal Transfers in the Presence of Rearrangements by the Minimum Evolution Criterion

Hadas Birin a, Zohar Gal-Or a, Isaac Elias b and Tamir Tuller a,*

aSchool of Computer Science, Tel Aviv University, Tel Aviv, Israel.
bGoogle (work done while at the School of Computer Science and Communication, Royal Institute of Technology, Sweden).

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


  Abstract

Motivation: The evolution of viruses is very rapid and in addition to local point mutations (insertion, deletion, substitution) it also includes frequent recombinations, genome rearrangements, and horizontal transfer of genetic materials (HGTS) . Evolutionary analysis of viral sequences is therefore a complicated matter for two main reasons: First, due to HGTs and recombinations, the right model of evolution is a network and not a tree. Second, due to genome rearrangements, an alignment of the input sequences is not guaranteed. These facts encourage developing methods for inferring phylogenetic networks that do not require aligned sequences as input.

Results: In this work we present the first computational approach which deals with both genome earrangements and horizontal gene transfers and does not require a multiple alignment as input. We formalize a new set of computational problems which involve analyzing such complex models of evolution. We investigate their computational complexity, and devise algorithms for solving them. Moreover, we demonstrate the viability of our methods on several synthetic datasets as well as four biological datasets.

Availability: The code is available from the authors upon request.

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

Associate Editor: Prof. Keith Crandall

Received on June 7, 2007; revised on October 16, 2007; accepted on January 14, 2008

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




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.