Parallel computing for biological data [Elektronische Ressource] / vorgelegt von Markus Schmidberger

Markus Schmidberger

Sujets

• Mathematics

Informations

• Publié par: ludwig-maximilians-universitat_munchen
• Publié le: 01 janvier 2009
• Nombre de lectures: 23
• Poids de l'ouvrage: 9 Mo

Extrait

Parallel Computing for Biological Data
Markus Schmidberger
Dissertation
an der Fakultat fur Mathematik, Informatik und Statistik
der Ludwig{Maximilians{Universitat
Munchen
Munchen, den 11. August 2009Parallel Computing for Biological Data
Markus Schmidberger
Dissertation
an der Fakultat fur Mathematik, Informatik und Statistik
der Ludwig{Maximilians{Universitat
Munchen
vorgelegt von
Markus Schmidberger
aus Weilheim
Munchen, den 11. August 2009Erstgutachter: Prof. Dr. Ulrich Mansmann
Zweitgutachter: Prof. Dr. Friedrich Leisch
Tag der mundlichen Prufung: 18. November 2009 Contents
1 Introduction 1
2 Biological Data 5
2.1 Biological Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Microarray Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2.1 DNA Microarrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2.2 DNA Microarray Analysis Process . . . . . . . . . . . . . . . . . . . 9
2.2.3 Microarray Error Model . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3 Next-Generation Sequencing . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.3.1 Standard Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.3.2 High-Throughput Sequencing . . . . . . . . . . . . . . . . . . . . . 14
2.3.3 Analyses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.4 Other Biological Data & Analyses . . . . . . . . . . . . . . . . . . . . . . . 16
3 Bioinformatics Using R and Bioconductor 19
3.1 R and Bioconductor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.2 Analyses of DNA Microarray Data . . . . . . . . . . . . . . . . . . . . . . 20
3.2.1 Low Level Analysis - Preprocessing . . . . . . . . . . . . . . . . . . 20
3.2.2 High Level Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.2.3 Computational Problems & Challenges . . . . . . . . . . . . . . . . 29
3.3 Next-Generation Sequence Data . . . . . . . . . . . . . . . . . . . . . . . . 33
3.3.1 Available Bioconductor Packages . . . . . . . . . . . . . . . . . . . 33
3.3.2 Computational Problems & Challenges . . . . . . . . . . . . . . . . 35
3.4 Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.4.1 Existing Bioconductor Solutions . . . . . . . . . . . . . . . . . . . . 36
3.4.2 Further Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4 Parallel Computing using R 39
4.1 Introduction to Parallel Computing . . . . . . . . . . . . . . . . . . . . . . 40
4.1.1 The Use of Parallel Computing . . . . . . . . . . . . . . . . . . . . 41
4.2 Parallel Hardware Environments . . . . . . . . . . . . . . . . . . . . . . . . 42
4.3 Parallel Software Environments . . . . . . . . . . . . . . . . . . . . . . . . 43
4.3.1 Shared Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44vi CONTENTS
4.3.2 Distributed Memory . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.3.3 Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.4 Parallel Program Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.4.1 Analysing the Serial Code . . . . . . . . . . . . . . . . . . . . . . . 47
4.4.2 Partitioning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.4.3 Further Aspects for Parallel Program Design . . . . . . . . . . . . . 48
4.5 Parallel Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.5.1 Computation Time . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.5.2 Speedup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.5.3 E ciency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.5.4 Karp-Flatt Metric . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.5.5 Resource Requirements . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.6 Parallel Computing using R . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.6.1 The snow Package . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.6.2 The multicore Package . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.7 Used Cluster Environments . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.7.1 Comparison of Used Cluster Environments . . . . . . . . . . . . . . 56
4.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5 Parallel Computing in Microarray Data: a yPara 59
5.1 Idea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
5.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
5.2.1 Basic Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
5.2.2 Background Correction . . . . . . . . . . . . . . . . . . . . . . . . . 61
5.2.3 Normalization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.2.4 Summarization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
5.2.5 Composite Preprocessing . . . . . . . . . . . . . . . . . . . . . . . . 70
5.2.6 Quality Control & Assessment . . . . . . . . . . . . . . . . . . . . . 72
5.3 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
5.3.1 Partition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
5.3.2 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . 76
5.3.3 Comparison to other Solutions . . . . . . . . . . . . . . . . . . . . . 79
5.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
6 Parallel Computing in Next-Generation Sequence Data 83
6.1 Ideas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
6.2 Parallelization in the ShortRead Package . . . . . . . . . . . . . . . . . . . 84
6.3 Parallelization in the BSgenome Package . . . . . . . . . . . . . . . . . . . 85
6.3.1 Parallel Implementation . . . . . . . . . . . . . . . . . . . . . . . . 85
6.3.2 Results & Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . 86
6.3.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
6.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91List of Contents vii
7 Large Cancer Study 93
7.1 Biological Question(s) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
7.1.1 Pathways . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
7.2 Data Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
7.2.1 Public Microarray Databases . . . . . . . . . . . . . . . . . . . . . 96
7.2.2 Data Set Description . . . . . . . . . . . . . . . . . . . . . . . . . . 99
7.2.3 Data Management: ArrayExpressDataManage . . . . . . . . . . . . 102
7.3 Analyses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
7.3.1 Analysis Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
7.3.2 Batch E ect . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
7.3.3 From Probes to Genes . . . . . . . . . . . . . . . . . . . . . . . . . 110
7.3.4 Inuence of Batch E ect and Preprocessing . . . . . . . . . . . . . 111
7.3.5 VSN Add-on Normalization . . . . . . . . . . . . . . . . . . . . . . 111
7.3.6 Simulation Study for Permutation Test of Array A liation . . . . . 113
7.4 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
7.4.1 Di erential Gene Expression . . . . . . . . . . . . . . . . . . . . . . 115
7.4.2 Correlation for Hemic Cancer Entities . . . . . . . . . . . . . . . . 117
7.4.3 Correlation for Solid Cancer Entities . . . . . . . . . . . . . . . . . 121
7.4.4 Comparison of Correlation between Solid and Hemic Cancer Entities 124
7.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
8 Summary and Outlook 127
8.1 State of Development . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
8.2 Open Topics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
8.3 The Future is Parallel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
8.3.1 Cloud Computing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
8.3.2 GPGPU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
A Documentation of Appended DVD 133
B Description of the Large Cancer Data Set 135
C Vignettes 149
Bibliography 151
Acknowledgment 161
Curriculum Vitae 163viii List of ContentsList of Figures
2.1 The transcription process . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2 Two A ymetrix Microarray GeneChips for Human and Mouse Genome. . . 8
2.3 Illustration of the A ymetrix Microarray GeneChip design. . . . . . . . . . 9
2.4 Microarray data analysis process . . . . . . . . . . . . . . . . . . . . . . . . 10
2.5 Illumina genome analyzer ow cell. . . . . . . . . . . . . . . . . . . . . . . 14
2.6 Ungapped sequence alignment of eleven E. coli sequences dening a start
codon. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.7 Overview of sub