Biomedical Engineering Reference
In-Depth Information
Additional investigations on DMRFs led to two scalable proposals. To escape the
computationally demanding checking of the decomposability property, appropriate
moves were tailored by Verzilli et al. to preserve this property while browsing the search
space of DMRFs [5]. To move from a triangulated graph to another one, these authors
designed moves that involve changes in the sets of cliques and separators. In the merge
move, a randomly selected clique is merged with another one. The split move splits up
a non-singleton clique selected at random. More recently, Abel and Thomas used rules
coming from graph theory, to keep the graph decomposability property when sampling
in the neighbourhood of a DMRF [13]. The authors are able to enumerate all the DMRF
neighbours of an incombent DMRF. Central to this enumeration is the concept of junc-
tion tree (JT): sampling in the space of JTs is substituted to sampling in the space of
DMRFs [14].
To reach scalability in LD modeling, the recent BN-based proposal of Mourad et al.
constrains the model structure to be a forest of latent tree models. Thus, a specific algo-
rithm may be tailored to efficiently learn the structure. We recapitulate the approaches
abovementioned in Table 1.
Ta b l e 1 . Probabilistic graphical models dedicated to the modeling of linkage disequilibrium
Scalability
Model
Main aim
Model learning
Details
Reference
Software
Markov random
field
LD modeling
Thomas and Camp (2004)
HapGraph
Hill climbing
Selection of
tagging SNPs
Greedy sparse
candidate procedure
-
Bayesian network
Lee and Shatkay (2006)
High density
LD mapping
Block partitioning, local Gibbs
sampling, Markov chain
Greenspan and Geiger (2004)
Haploclock
No
Bayesian
network with
latent variables
LD modeling
and phase
inference
SEM
Block-based collection of latent
class models
Kimmel and Shamir (2005)
-
Cluster-based collection of latent
class models
LD modeling
Zhang and Ji (2009)
-
Daly et al. (2001)
LD modeling
-
Hidden Markov
Model
Phase
inference,
missing data
imputation
EM
Scheet and Stephens (2006)
fastPHASE
Variable Length
Markov Chain
Genome-wide
association
study
Specific heuristic
Probabilistic automaton
Browning and Browning (2007)
Beagle
Ye s
Monte Carlo Markov
chain
Verzilli et al. (2006)
Markov random
field
Genome-scale
LD modeling
Sampling in the space of junction
trees
Hill climbing
Abel and Thomas (2011)
LD modeling,
dimension
reduction
Forest of latent
tree models
Specific procedure
Ascending clustering of variables
Mourad et al. (2010)
CFHLC+
3.3
Learning Latent Tree Models
As for general BNs, besides learning of parameters ( θ ), i.e. a priori and conditional
probabilities, one of the tasks in LTM learning is structure inference. This task gene-
rally remains the most challenging due to the complexity of the search space. Regarding
LTM learning, the proposals published in the literature fall into two categories. The first
category relies on standard Bayesian network learning techniques. The second category
is based on the clustering of the variables. To learn θ , both categories rely on the expec-
tation maximization (EM) algorithm or an EM variant.
 
Search WWH ::




Custom Search