Sorting genomes with rearrangements and segmental duplications through trajectory graphs.

Mingfu Shao, Y. Lin, Bernard Moret

Research output: Contribution to journalArticlepeer-review

12 Scopus citations


We study the problem of sorting genomes under an evolutionary model that includes genomic rearrangements and segmental duplications. We propose an iterative algorithm to improve any initial evolutionary trajectory between two genomes in terms of parsimony. Our algorithm is based on a new graphical model, the trajectory graph, which models not only the final states of two genomes but also an existing evolutionary trajectory between them. We show that redundant rearrangements in the trajectory correspond to certain cycles in the trajectory graph, and prove that our algorithm converges to an optimal trajectory for any initial trajectory involving only rearrangements.

Original languageEnglish (US)
Article numberS9
Pages (from-to)S9
JournalBMC bioinformatics
Volume14 Suppl 15
StatePublished - 2013

All Science Journal Classification (ASJC) codes

  • Structural Biology
  • Biochemistry
  • Molecular Biology
  • Computer Science Applications
  • Applied Mathematics


Dive into the research topics of 'Sorting genomes with rearrangements and segmental duplications through trajectory graphs.'. Together they form a unique fingerprint.

Cite this