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