Format

Send to

Choose Destination
See comment in PubMed Commons below
BMC Bioinformatics. 2013;14 Suppl 5:S7. doi: 10.1186/1471-2105-14-S5-S7. Epub 2013 Apr 10.

De Bruijn Superwalk with Multiplicities Problem is NP-hard.

Author information

1
St. Petersburg National Research University of Information Technologies, Mechanics and Optics Genome Assembly Algorithms Laboratory, Kronverksky pr. 49, St. Petersburg, Russia.

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.

PMID:
23734822
PMCID:
PMC3622630
DOI:
10.1186/1471-2105-14-S5-S7
[Indexed for MEDLINE]
Free PMC Article
PubMed Commons home

PubMed Commons

0 comments
How to join PubMed Commons

    Supplemental Content

    Full text links

    Icon for BioMed Central Icon for PubMed Central
    Loading ...
    Support Center