Genomic Signal Processing

Preface ix Chapter 1: Biological Foundations 1.1 Genetics 1 1.1.1 Nucleic Acid Structure 2 1.1.2 Genes 5 1.1.3 RNA 6 1.1.4 Transcription 6 1.1.5 Proteins 9 1.1.6 Translation 10 1.1.7 Transcriptional Regulation 12 1.2 Genomics 16 1.2.1 Microarray Technology 17 1.3 Proteomics 20 Bibliography 22 Chapter 2: Deterministic Models of Gene Networks 2.1 Graph Models 23 2.2 Boolean Networks 30 2.2.1 Cell Differentiation and Cellular Functional States 33 2.2.2 Network Properties and Dynamics 35 2.2.3 Network Inference 49 2.3 Generalizations of Boolean Networks 53 2.3.1 Asynchrony 53 2.3.2 Multivalued Networks 56 2.4 Differential Equation Models 59 2.4.1 A Differential Equation Model Incorporating Transcription and Translation 62 2.4.2 Discretization of the Continuous Differential Equation Model 65 Bibliography 70 Chapter 3: Stochastic Models of Gene Networks 3.1 Bayesian Networks 77 3.2 Probabilistic Boolean Networks 83 3.2.1 Definitions 86 3.2.2 Inference 97 3.2.3 Dynamics of PBNs 99 3.2.4 Steady-State Analysis of Instantaneously Random PBNs 113 3.2.5 Relationships of PBNs to Bayesian Networks 119 3.2.6 Growing Subnetworks from Seed Genes 125 3.3 Intervention 129 3.3.1 Gene Intervention 130 3.3.2 Structural Intervention 140 3.3.3 External Control 145 Bibliography 151 Chapter 4: Classification 4.1 Bayes Classifier 160 4.2 Classification Rules 162 4.2.1 Consistent Classifier Design 162 4.2.2 Examples of Classification Rules 166 4.3 Constrained Classifiers 168 4.3.1 Shatter Coefficient 171 4.3.2 VC Dimension 173 4.4 Linear Classification 176 4.4.1 Rosenblatt Perceptron 177 4.4.2 Linear and Quadratic Discriminant Analysis 178 4.4.3 Linear Discriminants Based on Least-Squares Error 180 4.4.4 Support Vector Machines 183 4.4.5 Representation of Design Error for Linear Discriminant Analysis 186 4.4.6 Distribution of the QDA Sample-Based Discriminant 187 4.5 Neural Networks Classifiers 189 4.6 Classification Trees 192 4.6.1 Classification and Regression Trees 193 4.6.2 Strongly Consistent Rules for Data-Dependent Partitioning 194 4.7 Error Estimation 196 4.7.1 Resubstitution 196 4.7.2 Cross-validation 198 4.7.3 Bootstrap 199 4.7.4 Bolstering 201 4.7.5 Error Estimator Performance 204 4.7.6 Feature Set Ranking 207 4.8 Error Correction 209 4.9 Robust Classifiers 213 4.9.1 Optimal Robust Classifiers 214 4.9.2 Performance Comparison for Robust Classifiers 216 Bibliography 221 Chapter 5: Regularization 5.1 Data Regularization 225 5.1.1 Regularized Discriminant Analysis 225 5.1.2 Noise Injection 228 5.2 Complexity Regularization 231 5.2.1 Regularization of the Error 231 5.2.2 Structural Risk Minimization 233 5.2.3 Empirical Complexity 236 5.3 Feature Selection 237 5.3.1 Peaking Phenomenon 237 5.3.2 Feature Selection Algorithms 243 5.3.3 Impact of Error Estimation on Feature Selection 244 5.3.4 Redundancy 245 5.3.5 Parallel Incremental Feature Selection 249 5.3.6 Bayesian Variable Selection 251 5.4 Feature Extraction 254 Bibliography 259 Chapter 6: Clustering 6.1 Examples of Clustering Algorithms 263 6.1.1 Euclidean Distance Clustering 264 6.1.2 Self-Organizing Maps 265 6.1.3 Hierarchical Clustering 266 6.1.4 Model-Based Cluster Operators 268 6.2 Cluster Operators 269 6.2.1 Algorithm Structure 269 6.2.2 Label Operators 271 6.2.3 Bayes Clusterer 273 6.2.4 Distributional Testing of Cluster Operators 274 6.3 Cluster Validation 276 6.3.1 External Validation 276 6.3.2 Internal Validation 277 6.3.3 Instability Index 278 6.3.4 Bayes Factor 280 6.4 Learning Cluster Operators 281 6.4.1 Empirical-Error Cluster Operator 281 6.4.2 Nearest-Neighbor Clustering Rule 283 Bibliography 292 Index 295