# An Algorithm for Reading Dependencies from the Minimal Undirected Independence Map of a Graphoid that Satisfies Weak Transitivity

Jose M. Peña, Roland Nilsson, Johan Björkegren, Jesper Tegnér.

Year: 2009, Volume: 10, Issue: 38, Pages: 1071−1094

#### Abstract

We present a sound and complete graphical criterion for reading
dependencies from the minimal undirected independence map *G* of a
graphoid *M* that satisfies weak transitivity. Here, complete means
that it is able to read all the dependencies in *M* that can be
derived by applying the graphoid properties and weak transitivity to
the dependencies used in the construction of *G* and the
independencies obtained from *G* by vertex separation. We argue that
assuming weak transitivity is not too restrictive. As an intermediate
step in the derivation of the graphical criterion, we prove that for
any undirected graph *G* there exists a strictly positive discrete
probability distribution with the prescribed sample spaces that is
faithful to *G*. We also report an algorithm that implements the
graphical criterion and whose running time is considered to be at most
*O*(*n*^{2}(*e*+*n*)) for *n* nodes
and *e* edges. Finally, we illustrate how
the graphical criterion can be used within bioinformatics to identify
biologically meaningful gene dependencies.