Efficient algorithms for analyzing segmental duplications, deletions, and inversions in genomes

Crystal L. Kahn, Shay Mozes, Benjamin J. Raphael

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Segmental duplications, or low-copy repeats, are common in mammalian genomes. In the human genome, most segmental duplications are mosaics consisting of pieces of multiple other segmental duplications. This complex genomic organization complicates analysis of the evolutionary history of these sequences. Earlier, we introduced a genomic distance, called duplication distance, that computes the most parsimonious way to build a target string by repeatedly copying substrings of a source string. We also showed how to use this distance to describe the formation of segmental duplications according to a two-step model that has been proposed to explain human segmental duplications. Here we describe polynomial-time exact algorithms for several extensions of duplication distance including models that allow certain types of substring deletions and inversions. These extensions will permit more biologically realistic analyses of segmental duplications in genomes.

Original languageEnglish (US)
Title of host publicationAlgorithms in Bioinformatics - 9th International Workshop, WABI 2009, Proceedings
Pages169-180
Number of pages12
DOIs
StatePublished - Nov 2 2009
Externally publishedYes
Event9th International Workshop on Algorithms in Bioinformatics, WABI 2009 - Philadelphia, PA, United States
Duration: Sep 12 2009Sep 13 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5724 LNBI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other9th International Workshop on Algorithms in Bioinformatics, WABI 2009
CountryUnited States
CityPhiladelphia, PA
Period9/12/099/13/09

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Efficient algorithms for analyzing segmental duplications, deletions, and inversions in genomes'. Together they form a unique fingerprint.

Cite this