{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,2,17]],"date-time":"2023-02-17T16:09:12Z","timestamp":1676650152812},"reference-count":15,"publisher":"Oxford University Press (OUP)","issue":"18","license":[{"start":{"date-parts":[[2016,10,2]],"date-time":"2016-10-02T00:00:00Z","timestamp":1475366400000},"content-version":"vor","delay-in-days":2220,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/2.0\/uk\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010,9,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Segmental duplications &amp;gt; 1 kb in length with \u2265 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.<\/jats:p>\n               <jats:p>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.<\/jats:p>\n               <jats:p>Availability: \u00a0Supplementary information is available at http:\/\/www.cs.brown.edu\/people\/braphael\/supplements\/.<\/jats:p>\n               <jats:p>Contact: \u00a0clkahn@cs.brown.edu; braphael@cs.brown.edu.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btq368","type":"journal-article","created":{"date-parts":[[2010,9,7]],"date-time":"2010-09-07T17:41:46Z","timestamp":1283881306000},"page":"i446-i452","source":"Crossref","is-referenced-by-count":5,"title":["Parsimony and likelihood reconstruction of human segmental duplications"],"prefix":"10.1093","volume":"26","author":[{"given":"Crystal L.","family":"Kahn","sequence":"first","affiliation":[{"name":"1 Department of Computer Science and 2Center for Computational Molecular Biology, Brown University, Providence, RI, 02912, USA"}]},{"given":"Borislav H.","family":"Hristov","sequence":"additional","affiliation":[{"name":"1 Department of Computer Science and 2Center for Computational Molecular Biology, Brown University, Providence, RI, 02912, USA"}]},{"given":"Benjamin J.","family":"Raphael","sequence":"additional","affiliation":[{"name":"1 Department of Computer Science and 2Center for Computational Molecular Biology, Brown University, Providence, RI, 02912, USA"},{"name":"1 Department of Computer Science and 2Center for Computational Molecular Biology, Brown University, Providence, RI, 02912, USA"}]}],"member":"286","published-online":{"date-parts":[[2010,9,4]]},"reference":[{"key":"2023012508252485000_B1","doi-asserted-by":"crossref","first-page":"1061","DOI":"10.1038\/ng.437","article-title":"Personalized copy number and segmental duplication maps using next-generation sequencing","volume":"41","author":"Alkan","year":"2009","journal-title":"Nat. Genet."},{"key":"2023012508252485000_B2","doi-asserted-by":"crossref","first-page":"552","DOI":"10.1038\/nrg1895","article-title":"Primate segmental duplications: crucibles of evolution, diversity and disease","volume":"7","author":"Bailey","year":"2006","journal-title":"Nat. Rev. Genet."},{"key":"2023012508252485000_B3","doi-asserted-by":"crossref","first-page":"627","DOI":"10.1534\/genetics.108.099960","article-title":"Segmental duplications contribute to gene expression differences between humans and chimpanzees","volume":"182","author":"Blekhman","year":"2009","journal-title":"Genetics"},{"key":"2023012508252485000_B4","doi-asserted-by":"crossref","first-page":"564","DOI":"10.1145\/1109557.1109619","article-title":"On the tandem duplication-random loss model of genome rearrangement","volume-title":"Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Chaudhuri","year":"2006"},{"key":"2023012508252485000_B5","doi-asserted-by":"crossref","first-page":"442","DOI":"10.1016\/S0022-0000(02)00003-X","article-title":"Reconstructing an ancestral genome using minimum segments duplications and reversals","volume":"65","author":"El-Mabrouk","year":"2002","journal-title":"J. Comput. Syst. Sci."},{"key":"2023012508252485000_B6","first-page":"222","article-title":"Comparing sequences with segment rearrangements","volume-title":"Proceedings FST TCS '03","author":"Ergun","year":"2003"},{"key":"2023012508252485000_B7","doi-asserted-by":"crossref","first-page":"1361","DOI":"10.1038\/ng.2007.9","article-title":"Ancestral reconstruction of segmental duplications reveals punctuated cores of human genome evolution","volume":"39","author":"Jiang","year":"2007","journal-title":"Nat. Genet."},{"key":"2023012508252485000_B8","doi-asserted-by":"crossref","first-page":"i133","DOI":"10.1093\/bioinformatics\/btn292","article-title":"Analysis of segmental duplications via duplication distance","volume":"24","author":"Kahn","year":"2008","journal-title":"Bioinformatics"},{"key":"2023012508252485000_B9","first-page":"126","article-title":"A parsimony approach to analysis of human segmental duplications","volume":"14","author":"Kahn","year":"2009","journal-title":"Pac. Symp. Biocomput."},{"key":"2023012508252485000_B10","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1186\/1748-7188-5-11","article-title":"Efficient algorithms for analyzing segmental duplications with deletions and inversions in genomes","volume":"5","author":"Kahn","year":"2010","journal-title":"Algorithms Mol. Biol."},{"key":"2023012508252485000_B11","doi-asserted-by":"crossref","first-page":"462","DOI":"10.1089\/cmb.2007.A007","article-title":"Duplication and inversion history of a tandemly repeated genes family","volume":"14","author":"Lajoie","year":"2007","journal-title":"J. Comp. Bio."},{"key":"2023012508252485000_B12","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1016\/j.tcs.2004.02.039","article-title":"Genomic distances under deletions and insertions","volume":"325","author":"Marron","year":"2004","journal-title":"Theor. Comput. Sci."},{"key":"2023012508252485000_B13","doi-asserted-by":"crossref","first-page":"1105","DOI":"10.1002\/bip.360290621","article-title":"The equilibrium partition function and base pair binding probabilities for RNA secondary structure","volume":"29","author":"McCaskill","year":"1990","journal-title":"Biopolymers"},{"key":"2023012508252485000_B14","doi-asserted-by":"crossref","first-page":"2245","DOI":"10.1101\/gr.2693004","article-title":"Whole-genome analysis of Alu repeat elements reveals complex evolutionary history","volume":"14","author":"Price","year":"2004","journal-title":"Genome Res."},{"key":"2023012508252485000_B15","doi-asserted-by":"crossref","first-page":"909","DOI":"10.1093\/bioinformatics\/15.11.909","article-title":"Genome rearrangement with gene families","volume":"15","author":"Sankoff","year":"1999","journal-title":"Bioinformatics"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/26\/18\/i446\/48859170\/bioinformatics_26_18_i446.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/26\/18\/i446\/48859170\/bioinformatics_26_18_i446.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,25]],"date-time":"2023-01-25T08:26:42Z","timestamp":1674635202000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/26\/18\/i446\/205165"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,9,4]]},"references-count":15,"journal-issue":{"issue":"18","published-print":{"date-parts":[[2010,9,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btq368","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2010,9,15]]},"published":{"date-parts":[[2010,9,4]]}}}