LEARNING SNP DEPENDENCIES USING EMBEDDED BAYESIAN NETWORKS
Ara V. Neflan · 2006
This paper describes an e-cient, scalable method for learning nucleotide dependencies around SNP sites using Bayesian networks. The complexity of the network is reduced by introducing a set of hidden nodes that do not appear in the original model. The resulting model is an embedded Bayesian network that encodes both local and global dependencies between the observed variables and allows for structure and parameter learning on parallel machines from distributed data. The results of the proposed learning method are reported on both synthetic data and DNA sequences of the human genome. In this paper we describe a parallel approach to structure learning that uses an embedded Bayesian network. The embedded Bayesian network is a hi- erarchical network in which each node is a of another Bayesian network. A subset of these models using in both the parent and child layers hidden Markov models (HMM) and/or coupled HMMs was introduced in 1 for the purpose of face recognition. Assuming a known structure, the EM algorithm was used for learning the parameters of these models. In this paper we generalize the networks used for face recognition and describe a structure learning al- gorithm for the embedded Bayesian networks. The method presented here uses an existing data parti- tion to learn local structures and the global depen- dencies between these structures. The approach can be e-ciently implemented on machines with paral- lel architecture, and reduces the computational com- plexity by partitioning the number of variables con- sidered in the local structures. This paper is organized as follows. Section 2 presents the hill climbing approach to structure learning in Bayesian networks, Section 3 deflnes the embedded Bayesian network and its parameters, Sec- tion 4 describes the structure learning algorithm for the embedded Bayesian network, Section 5 describes the experimental results obtained on both synthetic and bioinformatics data, and Section 6 highlights the contributions of these paper and gives directions for future work.