Computational Comparison Studies of Quadratic Assignment Like Formulations for the In Silico Sequence Selection Problem in De Novo Protein Design

H. K. Fung, S. Rao, C. A. Floudas (), O. Prokopyev, P. M. Pardalos and F. Rendl
Additional contact information
H. K. Fung: Princeton University
S. Rao: Princeton University
C. A. Floudas: Princeton University
O. Prokopyev: University of Florida
P. M. Pardalos: University of Florida
F. Rendl: Universität Klagenfurt

Journal of Combinatorial Optimization, 2005, vol. 10, issue 1, No 4, 60 pages

Abstract: Abstract In this paper an O(n2) mathematical formulation for in silico sequence selection in de novo protein design proposed by Klepeis et al. (2003, 2004), in which the number of additional variables and linear constraints scales with the square of the number of binary variables, is compared to three O(n) formulations. It is found that the O(n2) formulation is superior to the O(n) formulations on most sequence search spaces. The superiority of the O(n2) formulation is due to the reformulation linearization techniques (RLTs), since the O(n2) formulation without RLTs is found to be computationally less efficient than the O(n) formulations. In addition, new algorithmic enhancing components of RLTs with inequality constraints, triangle inequalities, and Dead-End Elimination (DEE) type preprocessing are added to the O(n2) formulation. The current best O(n2) formulation, which is the original formulation from Klepeis et al. (2003, 2004) plus DEE type preprocessing, is proposed for in silico sequence search. For a test problem with a search space of 3.4×1045 sequences, this new improved model is able to reduce the required CPU time by 67%.

Keywords: peptide and protein design and discovery; drug design; in silico sequence selection; structure prediction; de novo protein design; optimization (search for similar items in EconPapers)
Date: 2005
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-005-1859-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:10:y:2005:i:1:d:10.1007_s10878-005-1859-8

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-005-1859-8

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().