On algorithmic complexity of biomolecular sequence assembly problem

Giuseppe Narzisi, Bud Mishra, Michael C. Schatz

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publicationAlgorithms for Computational Biology - First International Conference, AlCoB 2014, Proceedings
PublisherSpringer Verlag
Number of pages13
ISBN (Print)9783319079523
StatePublished - 2014
Event1st International Conference on Algorithms for Computational Biology, AlCoB 2014 - Tarragona, Spain
Duration: Jul 1 2014Jul 3 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8542 LNBI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other1st International Conference on Algorithms for Computational Biology, AlCoB 2014


  • Genome Assembly
  • NP-complete Problem
  • Optimality
  • Sequence Assembly Problem

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'On algorithmic complexity of biomolecular sequence assembly problem'. Together they form a unique fingerprint.

Cite this