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

Phylogenetic tree construction (Felsenstein J, 2004)

ADD COMMENT
3
Entering edit mode
7.3 years ago

Genotype imputation.

ADD COMMENT
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?

ADD REPLY
3
Entering edit mode
4.3 years ago

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

ADD COMMENT
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/

ADD COMMENT

Login before adding your answer.

Traffic: 2349 users visited in the last hour
Help About
FAQ
Access RSS
API
Stats

Use of this site constitutes acceptance of our User Agreement and Privacy Policy.

Powered by the version 2.3.6