This is a test version of Biostars. For the public version, visit https://www.biostars.org.
List of np-hard problems in biology/bioinformatics

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

np-hard algorithm problem
• 8,670 views • link
updated by cmdcolin cmdcolin • written by 11cwicks • 11cwicks

4 answers

Phylogenetic tree construction (Felsenstein J, 2004)

• 0 views • link
written by Christian Christian

Genotype imputation.

• 0 views • link
written by chrchang523 chrchang523

Checking the link, I see no clear reference that this is NP-Hard; is there a reference that has done a formal analysis of the computational complexity of geneotype imputation or demonstrates it can be reduced to a known NP-Hard problem?

• 0 views • link
written by greenstick • greenstick

The Double Digest Problem (DDP) for physical mapping of DNA (Goldstein & Waterman, 1987).

• 0 views • link
written by Andrzej Zielezinski Andrzej Zielezinski

Scaffolding as well as de novo assembly are formally NP hard but have many heuristics

"The prevalence of heuristic choices in assembly owes its origins partly to several well-known early results regarding its computational complexity [1, 2] (and further confirmed by recent studies [3, 4]) which suggest that most formal definitions of various assembly problems (such as contiging and scaffolding) are computationally intractable (NP-hard)" https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4864936/

• 0 views • link
written by cmdcolin cmdcolin

Log in to answer this question.

More posts like this