CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Minimum common string partition parameterized

Peter Damaschke (Institutionen för data- och informationsteknik, Datavetenskap, Bioinformatik (Chalmers) ; Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers))
8th Workshop on Algorithms in Bioinformatics WABI 2008, Lecture Notes in Bioinformatics Vol. 5251 (2008), p. 87-98.
[Konferensbidrag, refereegranskat]

Minimum Common String Partition (MCSP) and related problems are of interest in, e.g., comparative genomics, DNA fingerprint assembly, and ortholog assignment. Given two strings with equal symbol content, the problem is to partition one string into k blocks, k as small as possible, and to permute them so as to obtain the other string. MCSP is NP-hard, and only approximation algorithms are known. Here we show that MCSP is fixed-parameter tractable in suitable parameters, so that practical instances can be efficiently solved to optimality.

Nyckelord: comparative genomics, genome rearrangement, parameterized algorithm

Denna post skapades 2008-09-19. Senast ändrad 2015-02-11.
CPL Pubid: 74159