Fast computation of a string duplication history under no-breakpoint-reuse | Zendy

Broňa Brejová | Zendy; Martin Kravec | Zendy; Gad M. Landau | Zendy; Tomáš Vinař | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Fast computation of a string duplication history under no-breakpoint-reuse

Author(s) -

Broňa Brejová,

Martin Kravec,

Gad M. Landau,

Tomáš Vinař

Publication year - 2014

Publication title -

philosophical transactions of the royal society a mathematical physical and engineering sciences

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.074

H-Index - 169

eISSN - 1471-2962

pISSN - 1364-503X

DOI - 10.1098/rsta.2013.0133

Subject(s) - breakpoint , computer science , computation , string (physics) , reuse , gene duplication , theoretical computer science , physics , algorithm , biology , theoretical physics , genetics , chromosome , ecology , gene

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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research