A parsimony approach to analysis of human segmental duplications

Crystal L. Kahn, Benjamin J. Raphael

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

7 Scopus citations


Segmental duplications are abundant in the human genome, but their evolutionary history is not well-understood. The mystery surrounding them is due in part to their complex organization; many segmental duplications are mosaic patterns of smaller repeated segments, or duplicons. A two-step model of duplication has been proposed to explain these mosaic patterns. In this model, duplicons are copied and aggregated into primary duplication blocks that subsequently seed secondary duplications. Here, we formalize the problem of computing a duplication scenario that is consistent with the two-step model. We first describe a dynamic programming algorithm to compute the duplication distance between two strings. We then use this distance as the cost function in an integer linear program to obtain the most parsimonious duplication scenario. We apply our method to derive putative ancestral relationships between segmental duplications in the human genome.

Original languageEnglish (US)
Title of host publicationPacific Symposium on Biocomputing 2009, PSB 2009
Number of pages12
StatePublished - 2009
Externally publishedYes
Event14th Pacific Symposium on Biocomputing, PSB 2009 - Kohala Coast, HI, United States
Duration: Jan 5 2009Jan 9 2009

Publication series

NamePacific Symposium on Biocomputing 2009, PSB 2009


Other14th Pacific Symposium on Biocomputing, PSB 2009
Country/TerritoryUnited States
CityKohala Coast, HI

All Science Journal Classification (ASJC) codes

  • Computational Theory and Mathematics
  • Biomedical Engineering
  • General Medicine


Dive into the research topics of 'A parsimony approach to analysis of human segmental duplications'. Together they form a unique fingerprint.

Cite this