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

Entering edit mode

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

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)" https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4864936/

Loading Similar Posts

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

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?