License
When quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-26892
URL: http://drops.dagstuhl.de/opus/volltexte/2010/2689/
Go to the corresponding Portal


Bergeron, Anne ; Mixtacki, Julia ; Stoye, Jens

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

pdf-format:
Document 1.pdf (188 KB)


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.

BibTeX - Entry

@InProceedings{bergeron_et_al:DSP:2010:2689,
  author =	{Anne Bergeron and Julia Mixtacki and Jens Stoye},
  title =	{A New Linear Time Algorithm to Compute the Genomic Distance Via the Double Cut and Join Distance},
  booktitle =	{Structure Discovery in Biology: Motifs, Networks & Phylogenies},
  year =	{2010},
  editor =	{Alberto Apostolico and Andreas Dress and Laxmi Parida},
  number =	{10231},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2010/2689},
  annote =	{Keywords: Comparative genomics, genomic distance computation, HP theory}
}

Keywords: Comparative genomics, genomic distance computation, HP theory
Seminar: 10231 - Structure Discovery in Biology: Motifs, Networks & Phylogenies
Issue Date: 2010
Date of publication: 23.08.2010


DROPS-Home | Fulltext Search | Imprint Published by LZI