title: De Bruijn Superwalk with Multiplicities Problem is NP-hard.
abstract: De Bruijn Superwalk with Multiplicities Problem is the problem of finding a walk in the de Bruijn graph containing several walks as subwalks and passing through each edge the exactly predefined number of times (equal to the multiplicity of this edge). This problem has been stated in the talk by Paul Medvedev and Michael Brudno on the first RECOMB Satellite Conference on Open Problems in Algorithmic Biology in August 2012. In this paper we show that this problem is NP-hard. Combined with results of previous works it means that all known models for genome assembly are NP-hard.
authors.affiliation: St. Petersburg National Research University of Information Technologies, Mechanics and Optics Genome Assembly Algorithms Laboratory, Kronverksky pr. 49, St. Petersburg, Russia.
authors.forename: Evgeny
authors.initials: E
authors.lastname: Kapun
authors.forename: Fedor
authors.initials: F
authors.lastname: Tsarev
mesh_terms: D000465:Algorithms; D023281:Genomics / Q000379:methods*