List of np-hard problems in biology/bioinformatics
4
10
Entering edit mode
7.3 years ago
11cwicks ▴ 90

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
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 • 5.2k views
4
Entering edit mode
7.3 years ago
Christian ★ 3.0k

Phylogenetic tree construction (Felsenstein J, 2004)

3
Entering edit mode
7.3 years ago

Genotype imputation.

0
Entering edit mode
0
Entering edit mode

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?

3
Entering edit mode
4.3 years ago

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

1
Entering edit mode
4.0 years ago
cmdcolin ★ 1.5k

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/