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

In this chapter, we describe Stochastic MLNs, a simple model based on MLNs
that is able to deal with sequences of logical atoms. We also propose two algo-
rithms for inference and learning in SMLNs based on the iterated robust tabu search
metaheuristic. Finally, we model in SMLNs the problem of protein fold recognition
from sequences of protein secondary structure and show through some preliminary
experiments the promise of our approach.
The chapter is organized as follows: in Sect. 4.2 we introduce MNs and MLNs,
in Sect. 4.3 we describe existing learning approaches for MLNs, Sect. 4.4 introduces
Stochastic MLNs, Sect. 4.5 introduces the iterated local search (ILS) and robust tabu
search (RoTS) metaheuristic and the satisfiability solver iterated robust tabu search
(IRoTS) that combines both and describes how IRoTS can be used for Maximum
a posteriori (MAP) inference in MLNs instead of the Viterbi algorithm, Sect. 4.6
introduces Markov chain IRoTS (MC-IRoTS) for performing inference in MLNs,
Sect. 4.7 describes how protein sequences can be modeled in SMLNs. Section 4.8
presents some preliminary experiments, and Sect. 4.9 concludes with future work.

4.2 Markov Networks and Markov Logic Networks

A Markov Network (or Markov random field) represents a model for the joint
distribution of a set of variables X = (X 1 ,X 2 ,...,X n ) 2 [ 5 ] (in this chapter, we
deal only with discrete features and variables). The model is composed of an undi-
rected graph G and a set of potential functions. There is a node for each variable and
a potential function k for each clique in the graph (a clique in an undirected graph
G is a set of vertices V, such that for every two vertices in V, there exists an edge
connecting the two). A potential function is a non-negative real-valued function of
the state of the corresponding clique. The joint distribution defined by an MN is
given by the following:

Y

1
Z

P.X D x/ D

k .x fkg /; (4.1)

k

where x fkg is the state of the k th clique (i.e., the state of the variables that appear in
that clique). The partition function, denoted by Z ,is:
Z D X
x2

Y

k .x fkg / (4.2)

k

MNs are often represented as log-linear models, by replacing each clique potential
with an exponentiated weighted sum of features of the clique state. This replacement
gives the following:

0
@ X
j

1

1
Z

A

P.X D x/ D exp w j f j .x/ (4.3)