The protein threading problem with sequence amino acid interaction preferences is NP-complete

Lathrop, R. H. (1994). The protein threading problem with sequence amino acid interaction preferences is NP-complete. Protein Engineering, 7, 1059-1068.

Type

Journal article

Intellectual base

Primary research

Year

1994

DOI

10.1093/protein/7.9.1059

Link

https://doi.org/10.1093/protein/7.9.1059

Cited by

1 citation across 1 artifact.

Domain-specific

• Protein Threading
  • When pairwise contacts and flexible gaps are included, finding a globally optimal threading becomes computationally hard: Lathrop proved the corresponding decision problem NP-complete and the optimization problem NP-hard under those conditions.

Verification

This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.

Registry ID ref:b3e6b0fe1f8d · see in the full table