Biostar Beta. Not for public use.
Question: List of np-hard problems in biology/bioinformatics
Entering edit mode

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

ADD COMMENTlink 5.9 years ago 11cwicks • 90 • updated 2.6 years ago cmdcolin ♦ 1.2k
Entering edit mode

Phylogenetic tree construction (Felsenstein J, 2004)

ADD COMMENTlink 5.9 years ago Christian ♦ 2.8k
Entering edit mode

Genotype imputation.

ADD COMMENTlink 5.9 years ago chrchang523 5.2k
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 REPLYlink 15 months ago
• 10
Entering edit mode

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

ADD COMMENTlink 2.9 years ago a.zielezinski 8.6k
Entering edit mode

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

ADD COMMENTlink 2.6 years ago cmdcolin ♦ 1.2k

Login before adding your answer.

Similar Posts
Loading Similar Posts
Powered by the version 2.0