@inproceedings{4368529b2ba04f50bc0dc4e1ed8068f8,
title = "On algorithmic complexity of biomolecular sequence assembly problem",
abstract = "Because of its connection to the well-known NP-complete shortest superstring combinatorial optimization problem, the Sequence Assembly Problem (SAP) has been formulated in simple and sometimes unrealistic string and graph-theoretic frameworks. This paper revisits this problem by re-examining the relationship between the most common formulations of the SAP and their computational tractability under different theoretical frameworks. For each formulation we show examples of logically-consistent candidate solutions which are nevertheless unfeasible in the context of the underlying biological problem. This material is hoped to be valuable to theoreticians as they develop new formulations of SAP as well as of guidance to developers of new pipelines and algorithms for sequence assembly and variant detection.",
keywords = "Genome Assembly, NP-complete Problem, Optimality, Sequence Assembly Problem",
author = "Giuseppe Narzisi and Bud Mishra and Schatz, {Michael C.}",
year = "2014",
doi = "10.1007/978-3-319-07953-0_15",
language = "English (US)",
isbn = "9783319079523",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "183--195",
booktitle = "Algorithms for Computational Biology - First International Conference, AlCoB 2014, Proceedings",
note = "1st International Conference on Algorithms for Computational Biology, AlCoB 2014 ; Conference date: 01-07-2014 Through 03-07-2014",
}