List of np-hard problems in biology/bioinformatics

Question

[11cwicks]

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

Answer 1

[Christian]

Phylogenetic tree construction (Felsenstein J, 2004)

Answer 2

[chrchang523]

Genotype imputation.

[Istvan Albert]

Link: Genotype imputation. Annu Rev Genomics Hum Genet. 2009;

[greenstick]

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?

Answer 3

[Andrzej Zielezinski]

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

Answer 4

[cmdcolin]

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/