Fast computation of a string duplication history under no-breakpoint-reuse
Broňa Brejová, Martin Kravec, Gad M. Landau, Tomáš Vinař · Philosophical Transactions of the Royal Society A Mathematical Physical and Engineering Sciences · 2014
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.