Home
People
Papers
Software

For students (in Slovak):
Študijný program
Uplatnenie
Predmety
Seminár
Témy prác

Members of:
Bratislava Biocenter

Funding

Brona Brejova, Martin Kravec, Gad M. Landau, Tomas Vinar. Fast computation of a string duplication history under no-breakpoint-reuse. Philos Trans A Math Phys Eng Sci, 372(2016):20130133. 2014. Early version appeared at SPIRE 2011.

Download preprint: not available

Download from publisher: http://rsta.royalsocietypublishing.org/content/372/2016/20130133.short

Related web page: not available

Bibliography entry: BibTeX

See also: early version

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.