A message passing approach to Side Chain Positioning with applications in protein docking refinement

Mohammad Moghadasi; Dima Kozakov; Artem B. Mamonov; Pirooz Vakili; Sandor Vajda; Ioannis Ch Paschalidis

doi:10.1109/CDC.2012.6426600

A message passing approach to Side Chain Positioning with applications in protein docking refinement

Mohammad Moghadasi
, Dima Kozakov
, Artem B. Mamonov
, Pirooz Vakili
, Sandor Vajda
, Ioannis Ch Paschalidis

Applied Mathematics and Statistics

Boston University

Research output: Contribution to journal › Conference article › peer-review

3 Scopus citations

Abstract

We introduce a message-passing algorithm to solve the Side Chain Positioning (SCP) problem. SCP is a crucial component of protein docking refinement, which is a key step of an important class of problems in computational structural biology called protein docking. We model SCP as a combinatorial optimization problem and formulate it as a Maximum Weighted Independent Set (MWIS) problem. We then employ a modified and convergent belief-propagation algorithm to solve a relaxation of MWIS and develop randomized estimation heuristics that use the relaxed solution to obtain an effective MWIS feasible solution. Using a benchmark set of protein complexes we demonstrate that our approach leads to more accurate docking predictions compared to a baseline algorithm that does not solve the SCP.

Original language	English
Article number	6426600
Pages (from-to)	2310-2315
Number of pages	6
Journal	Proceedings of the IEEE Conference on Decision and Control
DOIs	https://doi.org/10.1109/CDC.2012.6426600
State	Published - 2012
Event	51st IEEE Conference on Decision and Control, CDC 2012 - Maui, HI, United States Duration: Dec 10 2012 → Dec 13 2012

Access to Document

10.1109/CDC.2012.6426600

Cite this

@article{66b8e17d1a9b4bd89b15d89a01858b42,

title = "A message passing approach to Side Chain Positioning with applications in protein docking refinement",

abstract = "We introduce a message-passing algorithm to solve the Side Chain Positioning (SCP) problem. SCP is a crucial component of protein docking refinement, which is a key step of an important class of problems in computational structural biology called protein docking. We model SCP as a combinatorial optimization problem and formulate it as a Maximum Weighted Independent Set (MWIS) problem. We then employ a modified and convergent belief-propagation algorithm to solve a relaxation of MWIS and develop randomized estimation heuristics that use the relaxed solution to obtain an effective MWIS feasible solution. Using a benchmark set of protein complexes we demonstrate that our approach leads to more accurate docking predictions compared to a baseline algorithm that does not solve the SCP.",

author = "Mohammad Moghadasi and Dima Kozakov and Mamonov, \{Artem B.\} and Pirooz Vakili and Sandor Vajda and Paschalidis, \{Ioannis Ch\}",

year = "2012",

doi = "10.1109/CDC.2012.6426600",

language = "English",

pages = "2310--2315",

journal = "Proceedings of the IEEE Conference on Decision and Control",

issn = "0191-2216",

note = "51st IEEE Conference on Decision and Control, CDC 2012 ; Conference date: 10-12-2012 Through 13-12-2012",

}

TY - JOUR

T1 - A message passing approach to Side Chain Positioning with applications in protein docking refinement

AU - Moghadasi, Mohammad

AU - Kozakov, Dima

AU - Mamonov, Artem B.

AU - Vakili, Pirooz

AU - Vajda, Sandor

AU - Paschalidis, Ioannis Ch

PY - 2012

Y1 - 2012

N2 - We introduce a message-passing algorithm to solve the Side Chain Positioning (SCP) problem. SCP is a crucial component of protein docking refinement, which is a key step of an important class of problems in computational structural biology called protein docking. We model SCP as a combinatorial optimization problem and formulate it as a Maximum Weighted Independent Set (MWIS) problem. We then employ a modified and convergent belief-propagation algorithm to solve a relaxation of MWIS and develop randomized estimation heuristics that use the relaxed solution to obtain an effective MWIS feasible solution. Using a benchmark set of protein complexes we demonstrate that our approach leads to more accurate docking predictions compared to a baseline algorithm that does not solve the SCP.

AB - We introduce a message-passing algorithm to solve the Side Chain Positioning (SCP) problem. SCP is a crucial component of protein docking refinement, which is a key step of an important class of problems in computational structural biology called protein docking. We model SCP as a combinatorial optimization problem and formulate it as a Maximum Weighted Independent Set (MWIS) problem. We then employ a modified and convergent belief-propagation algorithm to solve a relaxation of MWIS and develop randomized estimation heuristics that use the relaxed solution to obtain an effective MWIS feasible solution. Using a benchmark set of protein complexes we demonstrate that our approach leads to more accurate docking predictions compared to a baseline algorithm that does not solve the SCP.

UR - https://www.scopus.com/pages/publications/84874285359

U2 - 10.1109/CDC.2012.6426600

DO - 10.1109/CDC.2012.6426600

M3 - Conference article

AN - SCOPUS:84874285359

SN - 0191-2216

SP - 2310

EP - 2315

JO - Proceedings of the IEEE Conference on Decision and Control

JF - Proceedings of the IEEE Conference on Decision and Control

M1 - 6426600

T2 - 51st IEEE Conference on Decision and Control, CDC 2012

Y2 - 10 December 2012 through 13 December 2012

ER -

A message passing approach to Side Chain Positioning with applications in protein docking refinement

Abstract

Access to Document

Other files and links

Fingerprint

Cite this