## 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**; 10(May):1071--1094, 2009.

### 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.

[abs][pdf]