Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Experiment Videos

Solving and analyzing side-chain positioning problems using linear and integer programming.

Carleton L Kingsford1, Bernard Chazelle, Mona Singh

  • 1Department of Computer Science and the Lewis-Sigler Institute for Integrative Genomics, Princeton University Princeton, NJ 08544, USA.

Bioinformatics (Oxford, England)
|November 18, 2004
PubMed
Summary
This summary is machine-generated.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

FBApro: A fast, simple linear transformation for diverse metabolic modeling tasks.

ArXiv·2026
Same author

Fast, accurate construction of multiple sequence alignments from protein language embeddings.

bioRxiv : the preprint server for biology·2026
Same author

Single-cell transcriptomics reveals FXR1 as an actionable target for siRNA therapy in ovarian cancer.

Nature communications·2026
Same author

Preface.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same author

Metabolic Dysfunction-Associated Steatotic Liver Disease (MASLD): the interplay of gut microbiome, insulin resistance, and diabetes.

Frontiers in medicine·2025
Same author

eIF4E Enriched Extracellular Vesicles Induce Immunosuppressive Macrophages through HMGCR-Mediated Metabolic Rewiring.

Advanced science (Weinheim, Baden-Wurttemberg, Germany)·2025

Integer linear programming (ILP) and linear programming (LP) effectively solve side-chain positioning for protein modeling and design. LP quickly finds optimal solutions for native and homologous backbones, while ILP handles complex design challenges.

Area of Science:

  • Computational Biology
  • Structural Bioinformatics
  • Protein Engineering

Background:

  • Side-chain positioning is crucial for homology modeling and protein design.
  • Optimizing side-chain conformations with fixed backbones is computationally challenging (NP-complete).

Purpose of the Study:

  • To provide a practical context for the computational hardness of side-chain positioning.
  • To develop and evaluate efficient computational methods for this problem.

Main Methods:

  • Formulation of side-chain positioning using integer linear programming (ILP).
  • Development of a linear programming (LP) heuristic by relaxing the ILP integrality constraint.
  • Application of LP and ILP to side-chain positioning on native/homologous backbones and protein design.

Related Experiment Videos

Main Results:

  • LP efficiently finds optimal side-chain positions for native and homologous backbones with simple energy functions.
  • The LP heuristic is often insufficient for the protein design problem.
  • ILP successfully solves complex protein design instances, even for large datasets.
  • LP/ILP approaches demonstrate high effectiveness in finding optimal and near-optimal solutions across various energy functions.

Conclusions:

  • LP-based methods are highly effective for optimizing side-chain positioning in protein modeling.
  • ILP provides a robust solution for challenging protein design problems.
  • This study offers the first large-scale validation of LP/ILP for side-chain positioning.