title: Comparing genomes with rearrangements and segmental duplications.
abstract: BACKGROUND
  Large-scale evolutionary events such as genomic rearrange.ments and segmental duplications form an important part of the evolution of genomes and are widely studied from both biological and computational perspectives. A basic computational problem is to infer these events in the evolutionary history for given modern genomes, a task for which many algorithms have been proposed under various constraints. Algorithms that can handle both rearrangements and content-modifying events such as duplications and losses remain few and limited in their applicability.
  
  
  RESULTS
  We study the comparison of two genomes under a model including general rearrangements (through double-cut-and-join) and segmental duplications. We formulate the comparison as an optimization problem and describe an exact algorithm to solve it by using an integer linear program. We also devise a sufficient condition and an efficient algorithm to identify optimal substructures, which can simplify the problem while preserving optimality. Using the optimal substructures with the integer linear program (ILP) formulation yields a practical and exact algorithm to solve the problem. We then apply our algorithm to assign in-paralogs and orthologs (a necessary step in handling duplications) and compare its performance with that of the state-of-the-art method MSOAR, using both simulations and real data. On simulated datasets, our method outperforms MSOAR by a significant margin, and on five well-annotated species, MSOAR achieves high accuracy, yet our method performs slightly better on each of the 10 pairwise comparisons.
  
  
  METHODS
  http://lcbb.epfl.ch/softwares/coser.
authors.affiliation: School of Computer and Communication Sciences, EPFL, CH-1015, Lausanne, Switzerland.
authors.forename: Mingfu
authors.initials: M
authors.lastname: Shao
authors.affiliation: School of Computer and Communication Sciences, EPFL, CH-1015, Lausanne, Switzerland.
authors.forename: Bernard M E
authors.initials: BM
authors.lastname: Moret
mesh_terms: D000465:Algorithms; D000818:Animals; D002875:Chromosomes; D019143:Evolution, Molecular; D023281:Genomics / Q000379:methods*; D006801:Humans; D051379:Mice; D011382:Programming, Linear; D051381:Rats; D056916:Segmental Duplications, Genomic