Computational Methods for Bioinformatics in Python 3.4

Computational Methods for Bioinformatics in Python 3.4


Jason M. Kinser, D.Sc.
George Mason University

 

Contents
Contents i
Preface 1
I Computing in Office Software 3
1 Mathematics Review 5
1.1 Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.1 Power Terms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.2 Calculator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.1.3 Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.1.4 Quadratic Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2 Geometry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3 Trigonometry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3.1 Coordinates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3.2 Triangles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.4 Linear Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.4.1 Elements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.4.2 Length . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.4.3 Addition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.4.4 Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.5 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2 Scientific Writing 19
iii
2.1 Content . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.1.1 Presentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.1.2 Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.1.3 Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.1.4 Equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2 Word Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2.1 MS - Word . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2.2 LATEX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2.2.1 Packages . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.2.2.2 Title . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.2.2.3 Headings . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.2.2.4 Cross References . . . . . . . . . . . . . . . . . . . . . . . . 25
2.2.2.5 Figures and Captions . . . . . . . . . . . . . . . . . . . . . 26
2.2.2.6 Equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.2.2.7 Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.2.2.8 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.2.2.9 Final Comments . . . . . . . . . . . . . . . . . . . . . . . . 30
2.2.3 LibreOffice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.2.4 Others . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.2.4.1 Google Docs . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.2.4.2 ABI Word . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.2.4.3 Zoho . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.2.4.4 WPS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3 Computing with a Spreadsheet 33
3.1 Creating Equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2 Cell Referencing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.2.1 Copying Formulas with References . . . . . . . . . . . . . . . . . . . 35
3.2.2 Absolute Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.2.3 Cell Names . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.3 Introduction to Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
iv
3.3.1 The Sum Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.3.2 Statistical Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.3.3 Comparison Functions . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.4 Creating Basic Plots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.5 Function Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.5.1 Trendline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.5.2 Solver . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4 Gene Expression Arrays: Excel 53
4.1 Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.2 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.3 Visualization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.4 Normalization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
4.5 Comparing Multiple Files . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
 

6.3 Python Collections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
6.3.1 Tuple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
6.3.2 List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
6.3.3 Dictionary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
6.3.4 Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
6.3.5 Slicing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
6.4 Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
6.4.1 String Definition and Slicing . . . . . . . . . . . . . . . . . . . . . . 86
6.4.1.1 Special Characters . . . . . . . . . . . . . . . . . . . . . . . 87
6.4.1.2 Concatenation . . . . . . . . . . . . . . . . . . . . . . . . . 87
6.4.1.3 Repeating Characters . . . . . . . . . . . . . . . . . . . . . 87
6.4.2 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
6.4.2.1 Replacing Characters . . . . . . . . . . . . . . . . . . . . . 89
6.4.2.2 Replacing Characters with a Table . . . . . . . . . . . . . . 90
6.5 Converting Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
6.6 Example: Romeo and Juliet . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
7 Python Logic Control 95
7.1 The if Command . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
7.1.1 The else Command . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
7.1.2 Complex Conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
7.1.3 The elif Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
7.2 Iterations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
7.2.1 The while Loop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
7.2.2 The for Loop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
7.2.3 break and continue . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
7.2.4 The enumerate Function . . . . . . . . . . . . . . . . . . . . . . . . 102
7.3 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
7.3.1 Example: The Average of Random Numbers . . . . . . . . . . . . . 102
7.3.2 Example: Text Search . . . . . . . . . . . . . . . . . . . . . . . . . . 104
7.3.3 Example: Sliding Block . . . . . . . . . . . . . . . . . . . . . . . . . 105
vi
7.3.4 Example: Compute π . . . . . . . . . . . . . . . . . . . . . . . . . . 106
7.3.5 Example: Summation Equations . . . . . . . . . . . . . . . . . . . . 108
7.4 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
8 Input and Output 111
8.1 Reading a File . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
8.2 Storing Data in a File . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
8.3 Moving the Position in the File . . . . . . . . . . . . . . . . . . . . . . . . . 113
8.4 Pickle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
8.5 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
8.5.1 Sliding Window in DNA . . . . . . . . . . . . . . . . . . . . . . . . . 115
8.5.2 Example: Reading a Spreadsheet . . . . . . . . . . . . . . . . . . . . 116
9 Python and Excel 121
9.1 Text Files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
9.2 The csv Module . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
9.3 xlrd . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
9.4 Openpyxl . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
9.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
10 Reading a Binary File 129
10.1 A Brief Overview of a Sequencer . . . . . . . . . . . . . . . . . . . . . . . . 129
10.2 Hexadecimal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
10.3 The ABI File Format . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
10.3.1 ABI Records . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
10.3.2 Extracting the Records . . . . . . . . . . . . . . . . . . . . . . . . . 136
10.3.2.1 The Base Calls . . . . . . . . . . . . . . . . . . . . . . . . . 136
10.3.2.2 The Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
10.3.3 Cohesive Program . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
11 Python Arrays 141
11.1 Vector . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
11.2 Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
vii
11.3 Slicing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
11.4 Mathematics and Some Functions . . . . . . . . . . . . . . . . . . . . . . . . 144
11.5 Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
11.6 Example: Extract Random Numbers Above a Threshold . . . . . . . . . . . 150
11.7 Indices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
11.8 Example: Simultaneous Equations . . . . . . . . . . . . . . . . . . . . . . . 155
12 Python Functions and Modules 159
12.1 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
12.1.1 Basic Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
12.1.2 Local and Global Variables . . . . . . . . . . . . . . . . . . . . . . . 160
12.1.3 Arguments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
12.1.4 Default Argument . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
12.1.5 Help Comments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
12.1.6 Return . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
12.1.7 Designing a Function . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
12.2 Modules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
12.3 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
13 Object Oriented Programming 173
13.1 Justification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
13.2 Basic Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
13.2.1 Class with a Function . . . . . . . . . . . . . . . . . . . . . . . . . . 174
13.2.2 Self . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
13.2.3 Global and Local Variables . . . . . . . . . . . . . . . . . . . . . . . 176
13.2.4 Operator Overloading . . . . . . . . . . . . . . . . . . . . . . . . . . 177
13.2.5 Inheritance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
13.2.6 Actively Adding a Variable . . . . . . . . . . . . . . . . . . . . . . . 180
14 Random Numbers 183
14.1 Simple Random Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
14.2 Randomness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184
viii
14.3 Gaussian Distributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
14.3.1 Gaussian Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
14.3.2 Gaussian Distributions in Excel . . . . . . . . . . . . . . . . . . . . . 187
14.3.3 Histogram in Python . . . . . . . . . . . . . . . . . . . . . . . . . . . 190
14.3.4 Random Gaussian Numbers . . . . . . . . . . . . . . . . . . . . . . . 190
14.4 Multivariate Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
14.5 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
14.5.1 Dice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
14.5.2 Cards . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
14.5.3 Random DNA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195

15.2 A Single File . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200
15.3 Multiple Files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203

16.1 DNA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
16.2 Application: Checking Genes . . . . . . . . . . . . . . . . . . . . . . . . . . 213
16.2.1 Reading the DNA File . . . . . . . . . . . . . . . . . . . . . . . . . . 213
16.2.2 Reading the Bounds File . . . . . . . . . . . . . . . . . . . . . . . . . 214
16.2.3 Examining the Data . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
17 Application in GC Content 219
17.1 Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219
17.2 Python Script . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219
17.3 Application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221
17.3.1 Non-Coding Regions . . . . . . . . . . . . . . . . . . . . . . . . . . . 222
17.3.2 Coding Regions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223
17.3.3 Preceding Region . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223
ix
17.3.4 Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224
18 DNA File Formats 227
18.1 FASTA Files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
18.2 Genbank Files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229
18.2.1 File Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229
18.2.2 Parsing the DNA String . . . . . . . . . . . . . . . . . . . . . . . . . 230
18.2.3 Keywords . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
18.2.4 Extracting Genes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232
18.2.5 Coding DNA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234
18.2.6 Extracting Translations . . . . . . . . . . . . . . . . . . . . . . . . . 234
18.3 ASN.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
18.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
19 Principle Component Analysis 241
19.1 The Purpose of PCA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241
19.2 Covariance Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242
19.2.1 Introduction to the Covariance Matrix . . . . . . . . . . . . . . . . . 242
19.2.2 An Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244
19.3 Eigenvectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245
19.4 Principal Component Analysis . . . . . . . . . . . . . . . . . . . . . . . . . 247
19.4.1 Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248
19.4.2 Projection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249
19.4.3 Python Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250
19.4.4 Distance Tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251
19.4.5 Organization in PCA . . . . . . . . . . . . . . . . . . . . . . . . . . . 252
19.4.6 RGB Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257
19.5 Describing Systems with Eigenvectors . . . . . . . . . . . . . . . . . . . . . 260
19.6 First Order Nature of PCA . . . . . . . . . . . . . . . . . . . . . . . . . . . 263
19.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263
20 Codon Frequencies in Genomes 265
x
20.1 Codon Frequency Vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265
20.1.1 Codon Table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265
20.1.2 Codon Counts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266
20.1.3 Codon Frequencies . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267
20.1.4 Frequencies of a Genome . . . . . . . . . . . . . . . . . . . . . . . . 267
20.2 Genome Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269
20.2.1 Single Genome . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269
20.2.2 Two Genomes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270
20.3 Comparing Multiple Genomes . . . . . . . . . . . . . . . . . . . . . . . . . . 271
21 Sequence Alignment 273
21.1 Simple Alignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274
21.1.1 An Alphabet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274
21.1.2 Considerations of Matching Sequences . . . . . . . . . . . . . . . . . 274
21.1.3 Insertions and Deletions . . . . . . . . . . . . . . . . . . . . . . . . . 274
21.1.3.1 Rearrangements . . . . . . . . . . . . . . . . . . . . . . . . 275
21.1.3.2 Sequence Length . . . . . . . . . . . . . . . . . . . . . . . . 275
21.1.4 Simple Alignments . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275
21.1.4.1 Direct Alignment . . . . . . . . . . . . . . . . . . . . . . . 276
21.2 Statistical Alignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 276
21.2.1 Substitution Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . 277
21.2.2 Accessing Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278
21.3 Brute Force Alignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279
21.4 Dynamic Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282
21.4.1 The Scoring Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . 284
21.4.2 The Arrow Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . 285
21.4.3 The Initial Program . . . . . . . . . . . . . . . . . . . . . . . . . . . 286
21.4.4 The Backtrace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287
21.4.5 Speed Considerations . . . . . . . . . . . . . . . . . . . . . . . . . . 288
21.5 Global and Local Alignments . . . . . . . . . . . . . . . . . . . . . . . . . . 293
21.6 Gap Penalties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294
xi
21.7 Optimality in Dynamic Programming . . . . . . . . . . . . . . . . . . . . . 296
21.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297
22 Simulated Annealing 301
22.1 Input to Output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301
22.2 Simulated Annealing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302
22.3 A Perpendicular Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305
22.4 Speed . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305
22.5 Meaningful Answers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307
22.6 Energy Surface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307
22.7 Text Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309
22.7.1 Swapping Letters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309
22.7.2 A Simple Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309
22.7.3 Consensus String . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312
23 Genetic Algorithms 317
23.1 Energy Surfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317
23.2 The Genetic Algorithm Approach . . . . . . . . . . . . . . . . . . . . . . . . 318
23.3 A Numerical GA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318
23.3.1 Initializing the Genes . . . . . . . . . . . . . . . . . . . . . . . . . . 319
23.3.2 The Cost Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319
23.3.3 The Crossover . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320
23.3.4 Mutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321
23.3.5 Running the GA Algorithm . . . . . . . . . . . . . . . . . . . . . . . 322
23.4 Non-Numerical GA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324
23.4.1 Manipulating the Strings . . . . . . . . . . . . . . . . . . . . . . . . 324
23.4.2 The Cost Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325
23.4.3 The Crossover . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326
23.4.4 Mutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 328
23.4.5 Running the GA for Text Data . . . . . . . . . . . . . . . . . . . . . 329
23.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329
xii
24 Multiple Sequence Alignment 331
24.1 Multiple Alignments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331
24.2 The Greedy Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332
24.2.1 Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333
24.2.2 Theory of the Assembly . . . . . . . . . . . . . . . . . . . . . . . . . 334
24.2.3 An Intricate Example . . . . . . . . . . . . . . . . . . . . . . . . . . 334
24.2.3.1 Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335
24.2.3.2 Pairwise Alignments . . . . . . . . . . . . . . . . . . . . . . 335
24.2.3.3 Initial Contigs . . . . . . . . . . . . . . . . . . . . . . . . . 337
24.2.3.4 Adding to a Contig . . . . . . . . . . . . . . . . . . . . . . 339
24.2.3.5 Joining Contigs . . . . . . . . . . . . . . . . . . . . . . . . 341
24.2.3.6 The Assembly . . . . . . . . . . . . . . . . . . . . . . . . . 343
24.3 The Non-Greedy Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . 345
24.3.1 Creating Genes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345
24.3.2 Steps in the Genetic Algorithm . . . . . . . . . . . . . . . . . . . . . 348
24.3.3 The Test Run . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 350
24.3.4 Improvements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352
24.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352
25 Trees 355
25.1 Dictionary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 355
25.2 Sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 356
25.3 Linked Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357
25.4 Binary Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 359
25.5 UPGMA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 364
25.6 Non-Binary Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 369
25.7 Decision Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 369
25.7.1 Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 370
25.7.2 Application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373
25.7.2.1 Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374
25.7.2.2 Scoring a Parameter . . . . . . . . . . . . . . . . . . . . . . 375
xiii
25.7.2.3 A Node . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 376
25.7.2.4 The Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . 378
25.7.2.5 A Trace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 380
26 Clustering 383
26.1 Purpose of Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383
26.2 k-Means Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 387
26.3 More Difficult Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 390
26.3.1 New Coordinate System . . . . . . . . . . . . . . . . . . . . . . . . . 393
26.3.2 Modification of k-means . . . . . . . . . . . . . . . . . . . . . . . . . 394
26.4 Dynamic k-means . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 396
26.5 Comments on k-means . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 401
26.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403

27.4 Methods of Finding Root Words . . . . . . . . . . . . . . . . . . . . . . . . 408
27.4.1 Porter Stemming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 408
27.4.2 Suffix Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 410
27.5 Document Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 410
27.5.1 Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 411
27.5.2 Word Frequency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 412
27.5.3 Indicative Words . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414
27.5.4 Document Classification . . . . . . . . . . . . . . . . . . . . . . . . . 417
27.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 417

28.1 The Movie Database . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 422
xiv
28.2 The Query List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 425
28.3 Answering the Queries in a Spreadsheet . . . . . . . . . . . . . . . . . . . . 426
29 Common Database Interfaces 437
29.1 Differences to a Spreadsheet . . . . . . . . . . . . . . . . . . . . . . . . . . . 437
29.2 Tables Required . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 437
29.3 Common Interfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 438
29.3.1 Microsoft Access . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 439
29.3.2 LibreOffice Base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 445
29.3.3 MySQL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 449
29.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 451
30 Fundamental Commands 453
30.1 Loading Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 453
30.1.1 Establishing a Database . . . . . . . . . . . . . . . . . . . . . . . . . 453
30.1.2 Creating a Table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 454
30.1.3 Loading Data into a Table . . . . . . . . . . . . . . . . . . . . . . . . 455
30.2 Updating . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456
30.3 Privileges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456
30.4 The Simple Query . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 457
30.4.1 Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 458
30.4.1.1 Integers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 459
30.4.1.2 Decimals . . . . . . . . . . . . . . . . . . . . . . . . . . . . 459
30.4.1.3 Floating Point . . . . . . . . . . . . . . . . . . . . . . . . . 459
30.4.1.4 Bit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 460
30.4.2 Default Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 460
30.4.3 Dates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 460
30.4.4 Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 460
30.4.5 Enumeration and Sets . . . . . . . . . . . . . . . . . . . . . . . . . . 461
30.4.6 Spatial Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 461
30.5 Conversions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 462
30.6 Mathematics in MySQL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 462
xv
30.6.1 Math Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 462
30.6.2 Math Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 463
30.6.3 Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 463
30.6.4 Hierarchy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 465
30.6.5 Aggregate Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . 465
30.6.6 Sample Queries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 465
30.7 String Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 469
30.8 Limits and Sorts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 472
30.9 Grouping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 474
30.10Time and Date . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 476
30.11Casting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 478
30.12Decisions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 478
30.12.1 CASE-WHEN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 479
30.12.2 The IF Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . 479
30.12.3 The IFNULL Statement . . . . . . . . . . . . . . . . . . . . . . . . . 480
30.12.4Natural Language Comparisons . . . . . . . . . . . . . . . . . . . . . 480
30.13Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 483
31 Queries with Multiple Tables 485
31.1 Schema and Linking Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . 485
31.1.1 Schema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 485
31.1.2 Linking Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 486
31.1.3 Combined with Functions . . . . . . . . . . . . . . . . . . . . . . . . 487
31.1.4 Using a Table Multiple Times . . . . . . . . . . . . . . . . . . . . . . 487
31.2 Joining Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 496
31.2.1 Left Join . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 497
31.2.2 Right Join . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 498
31.2.3 Other Joins . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 498
31.2.4 Functional Dependencies . . . . . . . . . . . . . . . . . . . . . . . . . 500
31.3 Subqueries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 500
31.4 Combinations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 501
xvi
31.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 504

32.1.1 Making the Connection . . . . . . . . . . . . . . . . . . . . . . . . . 505
32.1.2 Queries from Python . . . . . . . . . . . . . . . . . . . . . . . . . . . 506
32.1.3 Altering the Database . . . . . . . . . . . . . . . . . . . . . . . . . . 507
32.1.4 Multiple Queries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 507
32.2 The Kevin Bacon Effect . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 508
32.3 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 513