Brona Brejova, Gad M. Landau and Tomas Vinar. Fast Computation of a String Duplication History under No-Breakpoint-Reuse. In Roberto Grossi, Fabrizio Sebastiani, Fabrizio Silvestri, ed., String Processing and Information Retrieval (SPIRE), 7024 volume of Lecture Notes in Computer Science, pp. 144-155, Pisa, Italy, October 2011. Springer.
Download preprint: not available
Download from publisher: http://dx.doi.org/10.1007/978-3-642-24583-1_15
Related web page: not available
Bibliography entry: BibTeX
Abstract:
In this paper, we provide an O(n log2 n log log n log* n) algorithm to compute a duplication history of a string under no-breakpoint-reuse condition. Our algorithm is an efficient implementation of earlier work by Zhang et al. (2009). 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.
Last modified: 22.10.2011
Contact: Tomáš Vinař, KAI FMFI UK, Mlynská Dolina, 84248 Bratislava, Slovakia
Broňa Brejová, KI FMFI UK, Mlynská Dolina, 84248 Bratislava, Slovakia
Office: M-163 Phone: +421(2)60295207
E-mail: 