TY - GEN
T1 - Efficient algorithms for analyzing segmental duplications, deletions, and inversions in genomes
AU - Kahn, Crystal L.
AU - Mozes, Shay
AU - Raphael, Benjamin J.
N1 - Funding Information:
This work was partially funded by the Artemis Arrowhead project under grant agreement number 332987 (Artemis/Ecsel Joint Undertaking, supported by the European Commission and French Public Authorities).
PY - 2009
Y1 - 2009
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=70350417750&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=70350417750&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-04241-6_15
DO - 10.1007/978-3-642-04241-6_15
M3 - Conference contribution
AN - SCOPUS:70350417750
SN - 3642042406
SN - 9783642042409
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 169
EP - 180
BT - Algorithms in Bioinformatics - 9th International Workshop, WABI 2009, Proceedings
T2 - 9th International Workshop on Algorithms in Bioinformatics, WABI 2009
Y2 - 12 September 2009 through 13 September 2009
ER -