Biology Stack Exchange is a question and answer site for biology researchers, academics, and students. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm not sure if this is the right place for this but...

I am looking for a list of computationally "hard" problems such that if a problem from this list could be solved effectively, it would be (significantly, or otherwise) beneficial in some form or another to the biology community.

Some examples I have found (or atleast were tagged as "np-hard" problems):

Multiple sequence alignment problem
Protein threading / design problem
Map / sequence assembly problem

The list does not have to be extensive, but hopefully more than a few.

Thank you!

(Also, I couldn't think of any more tags to add so feel free to help out there as well.)

Note: Same question at biostars:

share|improve this question
Try asking this on, the people there probably have thought more often about the question if a problem is np-hard. – skymningen Apr 17 '14 at 6:49
Why has this question been downvoted? btw, this post might interest you @Colton – Remi.b Apr 17 '14 at 10:22
Just a curiosity: an NP-complete problem (Hamiltonian path) solved with molecular computing – Mattia Rovetta Apr 17 '14 at 11:40
Hope the below answer is somewhat helpful. – Bez May 25 '14 at 14:16
@MattiaRovetta Here is a related paper – user137 Nov 11 '15 at 0:37

I'm no expert in computational biology but I am very much interested and do some big data analysis using R for my own projects so I will try to provide some information.

This ( is an excellent book talking about all the grand challenges in computational biology and the emerging fields so I definitely recommend looking through at least the list on the page, if you don't want to read the entire book. To me all this points to the fact that we are in the big data era, where we have masses of data but making sense of them all and putting them into prospective and analysing them in a way to show us new insights into problems is difficult.

You might also be interested in BOINC, which runs a few computationally challenging projects through crowd sourcing/grid computing ( In more theoretical aspects, here is a list of unsolved problems (, solving of which will excel our understanding of many modelling problems, which percolate in biological problems as well although I'm not at all an expert in biological systems modelling.

Hope this helps!

share|improve this answer

De-novo assembly

To construct a genome from short reads, it's necessary to construct a graph of those reads. We do it by breaking the reads into k-mers and assemble them into a graph.

enter image description here

In this example, we have a k-mer of 3. We can reconstruct the genome by visiting each node once as in the diagram. This is known as Hamiltonian path.

Unfortunately, constructing such path is NP-hard. It's not possible to derive an efficient algorithm for solving it. Instead, in bioinformatics we construct a Eulerian cycle where an edge represents an overlap in two k-mers.

enter image description here

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.