Steps toward accurate reconstructions of phylogenies from gene-order data

Bernard M.E. Moret, Jijun Tang, Li San Wang, Tandy Warnow

Research output: Contribution to journalArticlepeer-review


We report on our progress in reconstructing phylogenies from gene-order data. We have developed polynomial-time methods for estimating genomic distances that greatly improve the accuracy of trees obtained using the popular neighbor-joining method; we have also further improved the running time of our GRAPPA software suite through a combination of tighter bounding and better use of the bounds. We present new experimental results (that extend those we presented at ISMB'01 and WABI'01) that demonstrate the accuracy and robustness of our distance estimators under a wide range of model conditions. Moreover, using the best of our distance estimators (EDE) in our GRAPPA software suite, along with more sophisticated bounding techniques, produced spectacular improvements in the already huge speedup: whereas our earlier experiments showed a one-million-fold speedup (when run on a 512-processor cluster), our latest experiments demonstrate a speedup of one hundred million. The combination of these various advances enabled us to conduct new phylogenetic analyses of a subset of the Campanulaceae family, confirming various conjectures about the relationships among members of the subset and confirming that inversion can be viewed as the principal mechanism of evolution for their chloroplast genome. We give representative results of the extensive experimentation we conducted on both real and simulated datasets in order to validate and characterize our approaches.

Original languageEnglish (US)
Pages (from-to)508-525
Number of pages18
JournalJournal of Computer and System Sciences
Issue number3
StatePublished - Nov 2002
Externally publishedYes


  • Ancestral genome
  • Breakpoint analysis
  • Distance estimator
  • Evolutionary distance
  • Genome rearrangement
  • Inversion distance

ASJC Scopus subject areas

  • Computational Theory and Mathematics


Dive into the research topics of 'Steps toward accurate reconstructions of phylogenies from gene-order data'. Together they form a unique fingerprint.

Cite this