Protein Fold Recognition Using Markov Logic Networks - Mathematical Approaches to Polymer Sequence Analysis and Related Problems - page 69

Chapter 4
Protein Fold Recognition Using Markov
Logic Networks

Marenglen Biba, Stefano Ferilli, and Floriana Esposito

Abstract Protein fold recognition is the problem of determining whether a given
protein sequence folds into a previously observed structure. An uncertainty com-
plication is that it is not always true that the structure has been previously ob-
served. Markov logic networks (MLNs) are a powerful representation that combines
first-order logic and probability by attaching weights to first-order formulas and us-
ing these as templates for features of Markov networks. In this chapter, we describe
a simple temporal extension of MLNs that is able to deal with sequences of log-
ical atoms. We also propose iterated robust tabu search (IRoTS) for maximum a
posteriori (MAP) inference and Markov Chain-IRoTS (MC-IRoTS) for conditional
inference in the new framework. We show how MC-IRoTS can also be used for
discriminative weight learning. We describe how sequences of protein secondary
structure can be modeled through the proposed language and show through some
preliminary experiments the promise of our approach for the problem of protein
fold recognition from these sequences.

4.1 Introduction

Protein fold recognition is the problem of determining whether a given protein
sequence folds into a previously observed structure. An uncertainty complication
is that it is not always true that the structure has been previously observed. There-
fore, there is strong motivation for developing machine learning methods that can
automatically infer models from already observed sequences in order to classify
new instances.
Dealing with sequential data has become an important application area of
machine learning. Such data are frequently found in computational biology, speech
recognition, activity recognition, information extraction, etc. One of the main