title: Parsimony and likelihood reconstruction of human segmental duplications.
abstract: BACKGROUND
  Segmental duplications > 1 kb in length with >or= 90% sequence identity between copies comprise nearly 5% of the human genome. They are frequently found in large, contiguous regions known as duplication blocks that can contain mosaic patterns of thousands of segmental duplications. Reconstructing the evolutionary history of these complex genomic regions is a non-trivial, but important task.
  
  
  RESULTS
  We introduce parsimony and likelihood techniques to analyze the evolutionary relationships between duplication blocks. Both techniques rely on a generic model of duplication in which long, contiguous substrings are copied and reinserted over large physical distances, allowing for a duplication block to be constructed by aggregating substrings of other blocks. For the likelihood method, we give an efficient dynamic programming algorithm to compute the weighted ensemble of all duplication scenarios that account for the construction of a duplication block. Using this ensemble, we derive the probabilities of various duplication scenarios. We formalize the task of reconstructing the evolutionary history of segmental duplications as an optimization problem on the space of directed acyclic graphs. We use a simulated annealing heuristic to solve the problem for a set of segmental duplications in the human genome in both parsimony and likelihood settings.
  
  
  BACKGROUND
  Supplementary information is available at http://www.cs.brown.edu/people/braphael/supplements/.
authors.affiliation: Department of Computer Science, Brown University, Providence, RI 02912, USA. clkahn@cs.brown.edu
authors.forename: Crystal L
authors.initials: CL
authors.lastname: Kahn
authors.forename: Borislav H
authors.initials: BH
authors.lastname: Hristov
authors.forename: Benjamin J
authors.initials: BJ
authors.lastname: Raphael
mesh_terms: D000465:Algorithms; D019143:Evolution, Molecular; D015894:Genome, Human; D006801:Humans; D008957:Models, Genetic; D015233:Models, Statistical; D011336:Probability; D056916:Segmental Duplications, Genomic
references.citation: J Comput Biol. 2007 May;14(4):462-78
references.pmid: 17572024
references.citation: Pac Symp Biocomput. 2009;:126-37
references.pmid: 19213134
references.citation: Nat Genet. 2007 Nov;39(11):1361-8
references.pmid: 17922013
references.citation: Algorithms Mol Biol. 2010 Jan 4;5(1):11
references.pmid: 20047668
references.citation: Bioinformatics. 1999 Nov;15(11):909-17
references.pmid: 10743557
references.citation: Genome Res. 2004 Nov;14(11):2245-52
references.pmid: 15520288
references.citation: Genetics. 2009 Jun;182(2):627-30
references.pmid: 19332884
references.citation: Nat Rev Genet. 2006 Jul;7(7):552-64
references.pmid: 16770338
references.citation: Bioinformatics. 2008 Aug 15;24(16):i133-8
references.pmid: 18689814
references.citation: Biopolymers. 1990 May-Jun;29(6-7):1105-19
references.pmid: 1695107
references.citation: Nat Genet. 2009 Oct;41(10):1061-7
references.pmid: 19718026