Seminár z teoretickej informatiky

Fri 11 Nov. 2011, 11:00

Title: Fast Computation of a String Duplication History Under No-Breakpoint-Reuse
Speaker: Broňa Brejová

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. 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.

Joint work with Gad M. Landau and Tomáš Vinař