Khai thác dữ liệu genomic bằng hàm boolean - Luận án tiến sĩ

GENOMIC DATA MINING ENHANCED BY SYMBOLIC MANIPULATION OF BOOLEAN FUNCTIONS A DISSERTATION SUBMITTED TO THE DEPARTMENT OF ELECTRICAL ENGINEERING AND THE COMMITTEE ON GRADUATE STUDIES OF STANFORD UNIVERSITY IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY Sungroh Yoon October 2005 UMI Number: 3197534 Copyright 2006 by Yoon, Sungroh All rights reserved. INFORMATION TO USERS The quality of this reproduction is dependent upon the quality of the copy submitted. Broken or indistinct print, colored or poor quality illustrations and photographs, print bleed-through, substandard margins, and improper alignment can adversely affect reproduction. In the unlikely event that the author did not send a complete manuscript and there are missing pages, these will be noted.

Also, if unauthorized copyright material had to be removed, a note will indicate the deletion. ® UMI UMI Microform 3197534 Copyright 2006 by ProQuest Information and Learning Company. All rights reserved. This microform edition is protected against unauthorized copying under Title 17, United States Code.

ProQuest Information and Learning Company 300 North Zeeb Road P. Box 1346 Ann Arbor, MI 48106-1346 © Copyright by Sungroh Yoon 2006 All Rights Reserved ii I certify that I have read this dissertation and that, in my opinion, it is fully adequate in scope and quality as a dissertation for the degree of Doctor of Philosophy. Ove he Atad' (le Ah hid. Giovanni De Micheli Principal Advisor I certify that I have read this dissertation and that, in my opinion, it is fully adequate in scope and quality as a dissertation for the degree of Doctor of Philosophy.

Altman I certify that I have read this dissertation and that, in my opinion, it is fully adequate in scope and quality as a dissertation for the degree of Doctor of Philosophy. L_ Oe: Luca Benini Approved for the University Committee on Graduate Studies. 1H To Hyeyoung iv Abstract Today, more and more large-scale genomic data sets are being produced by various high-throughput technologies, and genomic data mining has never been more impor- tant. Clustering is an unsupervised learning technique that has been popular in data analysis.

Although there is mature statistical literature on clustering, new types of genomic data such as gene expression data have sparked development of multiple new methods. Specifically, the technique of biclustering refers to a method that performs simultaneous clustering of rows and columns in a data matrix identifying patterns that appear in the form of (possibly overlapping) submatrices. Although this method has some clear advantages over conventional clustering techniques, it has been chal- lenging to develop an efficient biclustering algorithm, since the problem of biclustering is inherently intractable and hard to approximate. In the first part of this dissertation, a novel biclustering algorithm based upon the symbolic manipulation of Boolean functions is presented.

This algorithm exploits the zero-suppressed binary decision diagrams (ZBDDs) to implicitly represent and manipulate massive intermediate data that occur in the biclustering process. Lever- aged by the ZBDDs, the proposed algorithm can find all the biclusters that satisfy specific input parameters. The second part discusses the application of this algorithm to various genomic data mining tasks such as analyzing gene expression data, linking clinical traits with related genes, and predicting microRNA regulatory modules. The experimental results demonstrate that the proposed method outperforms the alterna- tive techniques tested — in terms of response time, the number of biclusters that can be found, and more importantly, how accurately the discovered biclusters conform to the known biological knowledge.

Acknowledgments First and foremost, I would like to thank my advisor Professor Giovanni De Micheli. From the very first moment when I knocked his door as a fresh PhD student, to the present day when I am planning my future career, he has never denied me his guidance, support and encouragement. I am greatly privileged to have him as my advisor. I would also like to thank Professor Russ Biagio Altman for serving as my co- advisor and Professor Luca Benini for serving on my dissertation committee.

Without the interaction with these two great mentors, my PhD research would have been severely compromised. In addition, I gratefully acknowledge Professor Edward J. McCluskey for super- vising my research for the Master’s degree and Professor Yoshio Nishi for serving as the chair of my oral defense committee. Special thanks also go to Professor and Mrs.

Creger for their continuous encouragement. Additional thanks go to Stanford CAD group members, EPFL LSI people, aca- demic collaborators, and friends. In particular, I would like to thank Eui-Young, Byung-Gon, and Nahmsuk for their invaluable help. I am also greatly indebted to Jerry Yang and Akiko Yamazaki for their vision and generous grant that supported my PhD research.

Last but not least, I would like to thank my wife Hyeyoung and my family (espe- cially Hongseop, Young, Byungsoh, Keumgyou, Hanyoung, Hyejin and Yeonsoo) for their never-ending love and support. vi Contents Abstract Acknowledgments vi 1 Introduction oDBEnOm 1. Q ng va và 1.3 Assumptions and limitations.v ưa kg KV 2 Background 2. eee eee ee eee 2.1 The flow of genetic information.

Q nà kg sa 2.3 Small non-coding RNAs .2 High-throughput biology.0 eee eee ne 2.2 Gene expression measuremenit.3 Biological data analysis and mining.1 Overview of machine learning .2 Challenges in large-scale data analysis .3 Previous work on biclustering .4 Symbolic manipulation of Boolean functions .1 Representations of Boolean functions .2 Zero-suppressed BDDs. ee ee ee ns A ZBDD-based Biclustering Algorithm 29 3. HQ gà k kg va 30 3.1 Characterization of biclusters .3 Formal definition of a bicluster and problem statement .2 Pairwise maximal biclusters (PMBs). eee ee ens 36 3.

ee Quà va 40 3.31 Relationship between G, FE, and seeds.2 Relationship between Gand BE. ee ee ee 41 3.4 Our biclustering algorithm .1 Predicting the experiment set E.2 Calculating the gene setG.3 Considerations for very large-scale expression data. ee ee 5ï Finding Nested Biclusters 4.1 Definitions and overview. eee eee ee ee ee 411 Definition of nested biclusters .2 Biology behind the definitions of biclusters .4 Overview of ourapproach .2 Finding atomic biclusters.1 Finding Type 1 atomic biclusters .2 Finding Type 2 atomic biclusters .3 Finding Type 3 atomic biclusters .3 Our bicluster mining algorithm .2 Representation and implementation of the functionJ .3 Finding nested biclusters.

ns DNA Microarray Data Analysis 5. pee ee ee 5. c ee ee ee 5. eee eee so 5.1 Algorithm performance evaluation.2 Bicluster quality evaluation.

ee eee 5= Sa | (aIIIAHAẠAA. Linking Gene Expression and Clinical Traits 6. ee ee kia 6.2 Correlation matrix computation.3 Defining co-clusters.4 Discovering pairwise co-clusters .5 Deriving co-cÌlusteTS. HQ gà kia 63 Experimental results.

Q Q và và và 6.000 eee eee nes 6.2 Results and discussion. LH LH HQ HQ ng kg kg A và và va ix 7 Prediction of MicroRNA Regulatory Modules 135 7.1 Identification of miRNA target sites.2 Relation graph representation.4 Deriving MRMs from seeds. Q Q eee ee ee 148 7. ee ee ee 149 7.2 Prediction and analysis of an oncogenic module .3 Supporting evidence from the literature.1 A strategy for biological validation .2 Extension of our computational method.

eee ee eee 158 8.2 Future work a HO CEO CO CO CÁ cm P9 CO B8 PB 8 8 8 8 8 8 Co 8 C8 8 Co C8 C9 161 Bibliography 163 List of Tables 3.1 Notations for PMB and seed. pee ee va 38 4.1 Classification of nested biclusters .2 Step 1 - finding atomic biclusters .3 Step 2 - deriving non-atomic biclusters .1 The bicluster mining methods tested in the experiments.2 The algorithm parameters used for the experiments .1 Definitions of the score rij.2 Parameters and statistics. ee ee và 127 6.3 Genes included in co-cluster #15 2. ee ee ee 133 6.4 Further details on an enriched GO term in Figure6.2 Example of MRMs.

QC Quy số 148 7.3 The parameters used for the experiment and some statistics obtained 150 7.4 A predicted human MRM .5 Details on an enriched GO term. eee ee ee 154 xi List of Figures 1.1 Growth of GenBank database .2 Informal comparison between clustering and biclustering .1 The flow of genetic information .2 DNA and its building blocks. Q LH ng Q v kg và 14 2.4 Mode of action of miRNAs in plants and animals .5 Manufacturing GeneChip® arrays.6 The curse of dimensionality .7 Difference between clinical and genomic studies .8 Representations of a Boolean logic function f=(at+b)e .9 Representation of a set of combinations.1 Characterization of biclusters. eee ee ee 32 3.3 Qualitative analysis of dependency ond.4 Pairwise maximal biclusters (PMBs) .6 ZBDD representation of verticalseeds.7 Relationship between Gand EF.8 Overview of the algorithm.

Q Q ngà và va na 46 xii 3.12 The trie representation of horizontal seeds and predicted EF sets .16 The operators U and @onZBDDs.17 Dividing a large data matrix. ee ee ee 55 4. Q và Là ki à v va 60 4.2 Example of Type 1 biclusters .3 Example of Type 2 biclusters ©. eee ee eee 63 4.4 Example of Type 3 biclusters.

ee eee ne 64 4.5 A flowchart of the algorithm. ee 69 4,7 Example: Algorithm 4. 00 eee ee eee eee 69 4. 2 eee ee ee 71 4.

vu 1v và k vV 73 4.12 Decomposition of Kg 2. ee ga vàn a 80 4.13 ZBDD representation of atomic bielusters.14 The process to find the biclusters presented in Figure 4.1 Biclusters found from the renal cell carcinoma data [42] .2 MSR scores as a measure of bicluster qualty.3 Performance comparison using synthetic datasets .4 Performance comparison using biological datasets.9 Box plots for MSR comparison.6 Correspondence plot and ROC curves.1 An example of co-clustering genes and clinical traits.2 A flowchart of the method .3 Construction of the correlation matrix .4 LIN-DEV versus the Pearson correlation coefficient .5 Defining co-clusters. cv Và kg sV 119 6.8 Prefix tree exampÌ©€.9 Composition of each images in Figure 6.10 Data from an adult acute myeloid leukemia (AML) study [17] .11 SAM plots obtained from the AML dataset.12 Annotations for co-cluster #15 2.1 MicroRNAs and targets [54] 2.2 Example of the relation graph and MRM. HQ HQ nu n n Q va kia 143 7.

Q Q Q Q HQ HH HQ nu Q v va à 146 7.5 Trie representation of the seeds. ee ee ee ee 147 7.6 Visualization of input data.7 Annotation of the human MRM with GO terms. 153 xiv Chapter 1 Introduction 1.1 Motivations High-throughput biology technologies such as DNA sequencing and gene expression measurement by DNA microarrays are producing a vast amount of biological informa- tion every day, and many researchers agree that biology is becoming an information science. In traditional biology, researchers usually pose a precise hypothesis and per- form well-defined experiments to test the hypothesis.

In contrast, in high-throughput biology, discoveries are data-driven, and data lead a hypothesis rather than the re- verse, Breakthroughs in high-throughput biotechnologies have already led to a rapid growth of biological data, both in size and complexity. For example, in recent years the rate at which the GenBank database! has grown exceeds the pace set by Moore’s Law” [73], as seen in Figure 1. As more and more biological data emerge, the emphasis progressively switches from the accumulation of data to its interpretation. The science of extracting useful information from large data sets or databases is known as data mining, which is one component in the area of machine learning and adaptive computation [37].

Defined more specifically, data mining is the analysis of ‘http://www.gov/Genbank ?The empirical observation that at our rate of technological development, the complexity of an integrated circuit, with respect to minimum component cost, will double in about 18 months. INTRODUCTION 2 #MÔ98#N (Smeiqlunocs) 8 6 44 2 wae Base Pairs —— Sequences (DoPBbaiNlsfrAen) 1882 1986 1990 1994 1998 2002 Figure 1.1: Growth of GenBank database. The growth rate exceeds the pace set by Moore’s Law [73].