Question: List of np-hard problems in biology/bioinformatics
10
gravatar for 11cwicks
3.3 years ago by
11cwicks90
United States
11cwicks90 wrote:

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

problem algorithm np-hard • 2.2k views
ADD COMMENTlink modified 3 days ago by cmdcolin640 • written 3.3 years ago by 11cwicks90
4
gravatar for Christian
3.3 years ago by
Christian2.5k
Vienna
Christian2.5k wrote:

Phylogenetic tree construction (Felsenstein J, 2004)

ADD COMMENTlink written 3.3 years ago by Christian2.5k
3
gravatar for chrchang523
3.3 years ago by
chrchang5232.4k
United States
chrchang5232.4k wrote:

Genotype imputation.

ADD COMMENTlink written 3.3 years ago by chrchang5232.4k

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

ADD REPLYlink written 3.3 years ago by Istvan Albert ♦♦ 73k
2
gravatar for a.zielezinski
3 months ago by
a.zielezinski7.0k
a.zielezinski7.0k wrote:

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

ADD COMMENTlink modified 3 months ago • written 3 months ago by a.zielezinski7.0k
1
gravatar for cmdcolin
3 days ago by
cmdcolin640
United States
cmdcolin640 wrote:

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 COMMENTlink modified 3 days ago • written 3 days ago by cmdcolin640
Please log in to add an answer.

Help
Access

Use of this site constitutes acceptance of our User Agreement and Privacy Policy.
Powered by Biostar version 2.3.0
Traffic: 791 users visited in the last hour