title: Phylogenetic reconstruction from transpositions.
abstract: BACKGROUND
  Because of the advent of high-throughput sequencing and the consequent reduction in the cost of sequencing, many organisms have been completely sequenced and most of their genes identified. It thus has become possible to represent whole genomes as ordered lists of gene identifiers and to study the rearrangement of these entities through computational means. As a result, genome rearrangement data has attracted increasing attentions from both biologists and computer scientists as a new type of data for phylogenetic analysis. The main events of genome rearrangements include inversions, transpositions and transversions. To date, GRAPPA and MGR are the most accurate methods for rearrangement phylogeny, both assuming inversion as the only event. However, due to the complexity of computing transposition distance, it is very difficult to analyze datasets when transpositions are dominant.
  
  
  RESULTS
  We extend GRAPPA to handle transpositions. The new method is named GRAPPA-TP, with two major extensions: a heuristic method to estimate transposition distance, and a new transposition median solver for three genomes. Although GRAPPA-TP uses a greedy approach to compute the transposition distance, it is very accurate when genomes are relatively close. The new GRAPPA-TP is available from http://phylo.cse.sc.edu/.
  
  
  CONCLUSIONS
  Our extensive testing using simulated datasets shows that GRAPPA-TP is very accurate in terms of ancestor genome inference and phylogenetic reconstruction. Simulation results also suggest that model match is critical in genome rearrangement analysis: it is not accurate to simulate transpositions with other events including inversions.
authors.affiliation: Department of Computer Science and Engineering, University of South Carolina, Columbia, SC 29208, USA. yuef@engr.sc.edu
authors.forename: Feng
authors.initials: F
authors.lastname: Yue
authors.forename: Meng
authors.initials: M
authors.lastname: Zhang
authors.forename: Jijun
authors.initials: J
authors.lastname: Tang
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D003198:Computer Simulation; D019143:Evolution, Molecular; D023061:Gene Order; D015321:Gene Rearrangement; D016678:Genome; D008957:Models, Genetic; D010802:Phylogeny