De Bruijn Superwalk with Multiplicities Problem is NP-hard

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...

Descripción completa

Detalles Bibliográficos
Autores principales: Kapun, Evgeny, Tsarev, Fedor
Formato: Online Artículo Texto
Lenguaje:English
Publicado: BioMed Central 2013
Materias:
Proceedings
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3622630/
https://www.ncbi.nlm.nih.gov/pubmed/23734822
http://dx.doi.org/10.1186/1471-2105-14-S5-S7
_version_ 1782265857140850688
author Kapun, Evgeny
Tsarev, Fedor
author_facet Kapun, Evgeny
Tsarev, Fedor
author_sort Kapun, Evgeny
collection PubMed
description 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.
format Online
Article
Text
id pubmed-3622630
institution National Center for Biotechnology Information
language English
publishDate 2013
publisher BioMed Central
record_format MEDLINE/PubMed
spelling pubmed-36226302013-04-15 De Bruijn Superwalk with Multiplicities Problem is NP-hard Kapun, Evgeny Tsarev, Fedor BMC Bioinformatics Proceedings 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. BioMed Central 2013-04-10 /pmc/articles/PMC3622630/ /pubmed/23734822 http://dx.doi.org/10.1186/1471-2105-14-S5-S7 Text en Copyright © 2013 Kapun and Tsarev; licensee BioMed Central Ltd. http://creativecommons.org/licenses/by/2.0 This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
spellingShingle Proceedings
Kapun, Evgeny
Tsarev, Fedor
De Bruijn Superwalk with Multiplicities Problem is NP-hard
title De Bruijn Superwalk with Multiplicities Problem is NP-hard
title_full De Bruijn Superwalk with Multiplicities Problem is NP-hard
title_fullStr De Bruijn Superwalk with Multiplicities Problem is NP-hard
title_full_unstemmed De Bruijn Superwalk with Multiplicities Problem is NP-hard
title_short De Bruijn Superwalk with Multiplicities Problem is NP-hard
title_sort de bruijn superwalk with multiplicities problem is np-hard
topic Proceedings
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3622630/
https://www.ncbi.nlm.nih.gov/pubmed/23734822
http://dx.doi.org/10.1186/1471-2105-14-S5-S7
work_keys_str_mv AT kapunevgeny debruijnsuperwalkwithmultiplicitiesproblemisnphard
AT tsarevfedor debruijnsuperwalkwithmultiplicitiesproblemisnphard

Ejemplares similares