Question: List of np-hard problems in biology/bioinformatics
10
gravatar for 11cwicks
4.1 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.9k views
ADD COMMENTlink modified 10 months ago by cmdcolin770 • written 4.1 years ago by 11cwicks90
4
gravatar for Christian
4.1 years ago by
Christian2.6k
Cambridge, US
Christian2.6k wrote:

Phylogenetic tree construction (Felsenstein J, 2004)

ADD COMMENTlink written 4.1 years ago by Christian2.6k
3
gravatar for chrchang523
4.1 years ago by
chrchang5233.4k
United States
chrchang5233.4k wrote:

Genotype imputation.

ADD COMMENTlink written 4.1 years ago by chrchang5233.4k

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

ADD REPLYlink written 4.1 years ago by Istvan Albert ♦♦ 76k
2
gravatar for a.zielezinski
13 months ago by
a.zielezinski8.3k
a.zielezinski8.3k wrote:

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

ADD COMMENTlink modified 13 months ago • written 13 months ago by a.zielezinski8.3k
1
gravatar for cmdcolin
10 months ago by
cmdcolin770
United States
cmdcolin770 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 10 months ago • written 10 months ago by cmdcolin770
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: 578 users visited in the last hour