A heuristic for phylogenetic reconstruction using transposition

Feng Yue*, Meng Zhang, Jijun Tang

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

Because of the advent of high-throughput sequencing and the consequent reduction in cost of sequencing, many organisms have been completely sequenced and most of their genes identified; homologies among these genes are also getting established. It thus has become possible to represent whole genomes as ordered lists of gene identifiers and to study the evolution of these entities through computational means, in systematics as well as in comparative genomics. As a result, gene order data (also known as genome rearrangement data) has attracted increasing attention from both biologists and computer scientists as a new type of data for phylogenetic analysis. Methods for reconstructing phylogeny from genome rearrangements include distance-based methods, MCMC methods and direct optimization methods. The latter, pioneered by Sankoff and extended in the software packages of GRAPPA and MGR, is the most accurate approach for inversion phylogeny. However, due to the difficulty of computing the transposition distance, this type of methods has not been applied to datasets where transposition is the only or dominant event. In this paper, we present a heuristic transposition median solver and extend GRAPPA to handle transpositions. Our extensive testing using simulated datasets shows that this method (GRAPPA-TP) is very accurate in terms of ancestor genome inference and phylogenetic reconstruction. It also suggests that model match is critical in phylogenetic analysis, and a fast and accurate method for transposition distance computation is still very important. The new GRAPPA-TP is available from phylo.cse.sc.edu.

Original languageEnglish (US)
Title of host publicationProceedings of the 7th IEEE International Conference on Bioinformatics and Bioengineering, BIBE
Pages802-808
Number of pages7
DOIs
StatePublished - 2007
Event7th IEEE International Conference on Bioinformatics and Bioengineering, BIBE - Boston, MA, United States
Duration: Jan 14 2007Jan 17 2007

Publication series

NameProceedings of the 7th IEEE International Conference on Bioinformatics and Bioengineering, BIBE

Other

Other7th IEEE International Conference on Bioinformatics and Bioengineering, BIBE
Country/TerritoryUnited States
CityBoston, MA
Period1/14/071/17/07

ASJC Scopus subject areas

  • Biotechnology
  • Genetics
  • Bioengineering

Fingerprint

Dive into the research topics of 'A heuristic for phylogenetic reconstruction using transposition'. Together they form a unique fingerprint.

Cite this