liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
An Algorithm for Reading Dependencies from the Minimal Undirected Independence Map of a Graphoid that Satisfies Weak Transitivity
Linköping University, Department of Computer and Information Science, Database and information techniques. Linköping University, The Institute of Technology. (ADIT)
Harvard University.
Karolinska Institute.
Linköping University, Department of Physics, Chemistry and Biology, Computational Biology. Linköping University, The Institute of Technology.
2009 (English)In: JOURNAL OF MACHINE LEARNING RESEARCH, ISSN 1532-4435, Vol. 10, 1071-1094 p.Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
2009. Vol. 10, 1071-1094 p.
Keyword [en]
graphical models, vertex separation, graphoids, weak transitivity, bioinformatics
National Category
Natural Sciences
URN: urn:nbn:se:liu:diva-51473OAI: diva2:275270
Available from: 2009-11-04 Created: 2009-11-04 Last updated: 2014-01-17

Open Access in DiVA

No full text

Other links

Link to Journal

Search in DiVA

By author/editor
Peña, Jose M.Tegnér, Jesper
By organisation
Database and information techniquesThe Institute of TechnologyComputational Biology
Natural Sciences

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 59 hits
ReferencesLink to record
Permanent link

Direct link