NDLI: SAT-based protein design

Content Provider	IEEE Xplore Digital Library
Author	Ollikainen, N. Sentovich, E. Coelho, C. Kuehlmann, A. Kortemme, T.
Copyright Year	2009
Description	Author affiliation: Department of Biopharmaceutical Sciences, University of California, San Francisco, CA (Ollikainen, N.; Kortemme, T.) \|\| Cadence Research Laboratories, Berkeley, CA (Coelho, C.; Kuehlmann, A.)
Abstract	Computational protein design can be formulated as an optimization problem, where the objective is to identify the sequence of amino acids that minimizes the energy of a given protein structure. In this paper, we propose a novel search-based approach that utilizes a Boolean function to encode the solution space where the function's onset represents the sequences considered during the search. We first present a dead-end-elimination (DEE) based method for the initial setup of the Boolean function and then describe a branch-and-bound algorithm that employs the search and deduction engine of a modern Boolean Satisfiability (SAT) solver. Its fast implication processing and conflict-based learning provide an efficient framework for the overall algorithm. Our results indicate that the presented approach can efficiently find the guaranteed optimum solution for protein core design problems. Furthermore, since our method is complete and symbolic, it can find all solutions that are within an ε-distance from the global minimum. This capability allows further analysis, such as identifying common sequence patterns of close-to-optimum solutions. Lastly, the SAT-based encoding of the search space provides a flexible mechanism to take complex design constraints into account, such as enforcing dependencies for amino acid choices at different positions or optimizing a single amino acid sequence to be simultaneously consistent with multiple input structures. Categories and Subject Descriptors: J.3 [Life and Medical Sciences]: Biology and genetics General Terms: Algorithms, Design
Starting Page	128
Ending Page	135
File Size	483295
Page Count	8
File Format	PDF
ISBN	9781605588001
ISSN	10923152
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2009-11-02
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Association for Computing Machinery, Inc. (ACM)
Subject Keyword	Amino acids Sequences Protein engineering Spine Design optimization Boolean functions Algorithm design and analysis Permission Biochemistry Laboratories Protein folding SAT Protein design
Content Type	Text
Resource Type	Article
Subject	Computer Graphics and Computer-Aided Design Computer Science Applications Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in