Graduate Theses and Dissertations
Graduate College
2012
Parallel Algorithms for Bayesian Networks Structure Learning with Applications in Systems Biology Olga Nikolova Iowa State University
Follow this and additional works at: http://lib.dr.iastate.edu/etd Part of the Bioinformatics Commons Recommended Citation Nikolova, Olga, "Parallel Algorithms for Bayesian Networks Structure Learning with Applications in Systems Biology" (2012). Graduate Theses and Dissertations. 12564. http://lib.dr.iastate.edu/etd/12564
This Dissertation is brought to you for free and open access by the Graduate College at Iowa State University Digital Repository. It has been accepted for inclusion in Graduate Theses and Dissertations by an authorized administrator of Iowa State University Digital Repository. For more information, please contact
[email protected] Parallel algorithms for Bayesian networks structure learning with applications in systems biology
by
Olga Nikolova
A dissertation submitted to the graduate faculty in partial fulfillment of the requirements for the degree of DOCTOR OF PHILOSOPHY
Major: Bioinformatics and Computational Biology
Program of Study Committee: Srinivas Aluru, Co-major Professor Patrick Schnable, Co-major Professor Dan Nettleton Julie Dickerson Guang Song
Iowa State University Ames, Iowa 2012 c Olga Nikolova, 2012. All rights reserved. Copyright
ii
DEDICATION
I dedicate this work to my parents, Svetlana Nikolova and Hristo Nikolov.
iii
TABLE OF CONTENTS
LIST OF FIGURES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
vi
LIST OF TABLES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
ix
LIST OF ALGORITHMS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
xi
ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
xiii
CHAPTER 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
1.1
1.2
Background and Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
1.1.1
Gene Regulatory Networks . . . . . . . . . . . . . . . . . . . . . . . . .
1
1.1.2
Bayesian Networks as a Model for Gene Regulatory Networks . . . . . .
3
1.1.3
Exact Bayesian Network Structure Learning . . . . . . . . . . . . . . . .
4
1.1.4
Heuristic Bayesian Network Structure Learning . . . . . . . . . . . . . .
6
Concepts of Bayesian Networks and Structure Learning . . . . . . . . . . . . .
7
1.2.1
Markov Assumption and Bayesian Networks . . . . . . . . . . . . . . . .
7
1.2.2
Optimal Structure Learning . . . . . . . . . . . . . . . . . . . . . . . . .
8
1.2.3
Scoring Functions
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
1.2.4
Faithfulness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
1.2.5
D-separation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
1.2.6
Constraints-based Learning . . . . . . . . . . . . . . . . . . . . . . . . .
13
iv 1.2.7
Markov Boundary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
1.2.8
Markov Equivalence . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
CHAPTER 2. Parallel Globally Optimal Structure Learning of B
