The goal of this work is to provide a novel probabilistic computational engine for docking-based virtual screening. The engine is based on probabilistic model of Markov Random Fieds (MRF). MRF's have proven successful in other fields such as Computer Vision, and can be seen as a 3D analog of the successful 1D application of Hidden Markov Models to bioinformatics. The docking of a rigid ligand or ligand fragment into a protein active site is modeled as a weighted graphical match of an abstracted description of the ligand to an abstracted description of the active site. These abstracted descriptions are graphs, whose nodes are chemical entities (hydrogen bond acceptors/donors, hydrophobic spheres and etc.) and whose edges are associated distance constraints. The weighted graph-matching problem is expressed as an MRF, whose solution minimizes its associated free energy function. A fast, convergent message-passing scheme called Belief Propagation is used to solve the MRF. The result is a probability distribution that describes all possible placements of the ligand into the active site. Individual low-energy placements of the molecule are obtained by marginalizing this probability distribution. The method provides a fast and mathematically complete examination of possible fits of the ligand into the protein active site, and our prototype MRF application demonstrates excellent timing and completeness properties. The method also provides an attractive data structure enabling a variety of applications. The data structure intrinsically admits an enriched description of the active site. This description can incorporate an extended set of chemical substructures for matching at its nodes. It also can incorporate sets of probabilistic beliefs, expressed as probabilistic prior distributions. These can be used to bias matches according to known actives. Our goals in Phase I are to further develop our prototype into a robust MRF-based docking engine to positioning rigid molecules and molecular fragments into protein active sites. Our goals in Phase II will be to implement applications based on the MRF docking engine: (i) inclusion flexible ligand docking, (ii) incorporation of flexible side chains into docking, (iii) de-novo ligand design, and (iv) docking into multiple aligned proteins. We will seek corporate partners interested in collaborating on applying the technologies to specific problems in drug discovery in Phase I1. The technology developed will be sold as commercial software in Phase III.
