title: Fast computation of a string duplication history under no-breakpoint-reuse.
abstract: In this paper, we provide an O(n log(2) n log log n log* n) algorithm to compute a duplication history of a string under no-breakpoint-reuse condition. The motivation of this problem stems from computational biology, in particular, from analysis of complex gene clusters. The problem is also related to computing edit distance with block operations, but, in our scenario, the start of the history is not fixed, but chosen to minimize the distance measure.
authors.affiliation: Faculty of Mathematics, Physics and Informatics, Comenius University, , Mlynská dolina, 842 48 Bratislava, Slovakia.
authors.forename: Broňa
authors.initials: B
authors.lastname: Brejová
authors.forename: Martin
authors.initials: M
authors.lastname: Kravec
authors.forename: Gad M
authors.initials: GM
authors.lastname: Landau
authors.forename: Tomaš
authors.initials: T
authors.lastname: Vinař
keywords: duplication; dynamic text; edit distance; sequence evolution
references.citation: J Comput Biol. 2007 May;14(4):462-78
references.pmid: 17572024
references.citation: Proc Natl Acad Sci U S A. 2008 Sep 23;105(38):14254-61
references.pmid: 18787111
references.citation: Proc Natl Acad Sci U S A. 1984 Feb;81(3):814-8
references.pmid: 6583681
references.citation: J Comput Biol. 2010 Sep;17(9):1227-42
references.pmid: 20874406
references.citation: J Comput Biol. 2010 Sep;17(9):1267-79
references.pmid: 20874408
references.citation: Algorithms Mol Biol. 2010 Jan 4;5(1):11
references.pmid: 20047668
references.citation: Mol Biol Evol. 2002 Mar;19(3):278-88
references.pmid: 11861887
references.citation: J Comput Biol. 2009 Aug;16(8):1051-70
references.pmid: 19645598