A New Linear Time Algorithm to Compute the Genomic Distance Via the Double Cut and Join Distance

Authors Anne Bergeron, Julia Mixtacki, Jens Stoye



PDF
Thumbnail PDF

File

DagSemProc.10231.2.pdf
  • Filesize: 188 kB
  • 25 pages

Document Identifiers

Author Details

Anne Bergeron
Julia Mixtacki
Jens Stoye

Cite AsGet BibTex

Anne Bergeron, Julia Mixtacki, and Jens Stoye. A New Linear Time Algorithm to Compute the Genomic Distance Via the Double Cut and Join Distance. In Structure Discovery in Biology: Motifs, Networks & Phylogenies. Dagstuhl Seminar Proceedings, Volume 10231, pp. 1-25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
https://doi.org/10.4230/DagSemProc.10231.2

Abstract

The genomic distance problem in the Hannenhalli-Pevzner (HP) theory is the following: Given two genomes whose chromosomes are linear, calculate the minimum number of translocations, fusions, fissions and inversions that transform one genome into the other. We will present a new distance formula based on a simple tree structure that captures all the delicate features of this problem in a unifying way, and a linear-time algorithm for computing this distance.
Keywords
  • Comparative genomics
  • genomic distance computation
  • HP theory

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail