Pattern Recognition in Bioinformatics: 5th IAPR International Conference, PRIB 2010, Nijmegen, The Netherlands, September 22-24, 2010, Proceedings (Lecture Notes in Computer Science, 6282)

This book constitutes the refereed proceedings of the 5th International Conference on Pattern Recognition in Bioinformatics, PRIB 2010, held in Nijmegen, The Netherlands, in September 2010. The 38 revised full papers presented were carefully reviewed and selected from 46 submissions. The field of bioinformatics has two main objectives: the creation and maintenance of biological databases and the analysis of life sciences data in order to unravel the mysteries of biological function. Computer science methods such as pattern recognition, machine learning, and data mining have a great deal to offer the field of bioinformatics. Title Page Preface Organization Table of Contents Part I: Classification of Biological Sequences Sequence-Based Prediction of Protein Secretion Success in A$spergillus niger$ Introduction Materials and Methods Data Set Sequence-Based Features Performance Evaluation Training and Validation Protocol Classifiers Results Operating Point Example Feature Optimization Feature Correlation Feature Selection Discussion References Machine Learning Study of DNA Binding by Transcription Factors from the LacI Family Introduction Materials and Methods Data Cross-Validation Algorithms Results and Discussion Selecting Site Alignment Positions Selection of Significant Positions AAS-Position Selection for Position 9 of the Site Alignment AAS-Position Selection for Position 7 of the Site Alignment AAS-Position Selection for Position 6 of the Site Alignment AAS-Position Selection for Position 5 of the Site Alignment Conclusions References Joint Loop End Modeling Improves Covariance Model Based Non-coding RNA Gene Search Introduction Covariance Model Structure and Parameter Estimation Model Structure Model Parameters Thermodynamic Regularities Changes to Model Structure and Estimation Experimental Results Conclusions References Structured Output Prediction of Anti-cancer Drug Activity Introduction Methods Structured Output Learning with MMCRF Kernels for Drug-Like Molecules Markov Network Generation for Cancer Cell Lines Experiments NCI-Cancer Dataset Data Preprocessing Experiment Setup Kernel Setup Results Effect of Markov Network Generation Methods Effect of molecule kernels Effect of Dataset Versions Agreement of MMCRF and SVM Predictions Computation Time Conclusions References SLiMSearch: A Webserver for Finding Novel Occurrences of Short Linear Motifs in Proteins, Incorporating Sequence Context Introduction The SLiMSearch Algorithm SLiMChance Calculations of Significance The SLiMSearch Webserver Input Masking Options Submitting Jobs Output Getting Help Server Limits Example Analysis: HOX Ligand Motif Future Work Conclusion References Towards 3D Modeling of Interacting TM Helix Pairs Based on Classification of Helix Pair Sequence Introduction Materials and Methods Datasets Principles and Formal Definitions Representation of Amino-Acid Properties Parsing Learning Method for Stochastic Context-Free Grammars Protocol for Evaluation of Transmembrane H-H Interaction Prediction Results and Discussion Performance of Classifiers on Independent Test Set Analysis of Classifiers Features Conclusions References Optimization Algorithms for Identification and Genotyping of Copy Number Polymorphisms in Human Populations Introduction Methods Problem Definition Identification of Candidate CNPs Identifying CNP Genotypes and Fine-Tuning of CNP Boundaries Algorithms for Optimal CNP Identification and Copy Number Genotyping Results Methods Used for Comparison Trio Discordance Comparison across Methods Sensitivity Comparison across Methods Conclusion References Preservation of Statistically Significant Patterns in Multiresolution 0-1 Data Introduction DNA Copy Number Amplification Dataset Theoretical Framework Sampling Resolutions Randomization Mixture Models of Multivariate Bernoulli Distribution Experiments Convergence Analysis of the Swaps Model Selection in Mixture Model Significance of Frequent Itemsets and Data Samples Effect of Noise on the Likelihood Summary and Conclusions References Novel Machine Learning Methods for MHC Class I Binding Prediction Introduction Improved String Kernels for MHC-I Binding Prediction A New Multitask Kernel for MHC-I Binding Prediction Fine Tuning the Kernel with Multiple Kernel Learning Experimental Methods Conclusion References Part II: Unsupervised Learning Methods for Biological Sequences SIMCOMP: A Hybrid Soft Clustering of Metagenome Reads Introduction Related Work An Overview of Methods and Algorithm Comparative Clustering Composition Based Clustering Definitions SIMCOMP : Outline of the Algorithm Results Accuracy across Taxonomic Ranks Length of Oligomer Read Threshold Conclusion References The Complexity and Application of Syntactic Pattern Recognition Using Finite Inductive Strings Introduction Review of FI Algorithms and Theory Generating and Applying the FI Algorithms Algorithm Overview Factoring Analysis Following Analysis Performance Analysis Empirical Performance Test Experiment Design Timing Results Application of FI Algorithm to Actual Data Conclusion References An Algorithm to Find All Identical Motifs in Multiple Biological Sequences Introduction Existing Algorithms Methodology Pre-processing Phase Searching Phase Post Processing Phase Time Complexity Results and Discussion Case Study 1 Case Study 2 Implementation Conclusion References Discovery of Non-induced Patterns from Sequences Introduction Related Work Methodology Preliminary Definitions Statistical Model for Input Sequences Characterizing Significant Representative Patterns in Generalized Suffix Tree Discovering Non-induced Patterns Experimental Results Experiment on Synthetic Data Experiment on Transcription Factor Binding Sites Conclusion and Future Work References Exploring Homology Using the Concept of Three-State Entropy Vector Introduction Materials and Methods DNA Sequences Finite-Context Models The Three-State Model Results Conclusion References A Maximum-Likelihood Formulation and EM Algorithm for the Protein Multiple Alignment Problem Introduction Dayhoff's PAM Model of Evolution within the Amino Acid Alphabet Model of the Common Origin of a Set of Proteins Maximum-Likelihood Estimation of the Common Profile Choosing Main Parameters of the Algorithm The Most Probable Multiple Alignment Experimental Results and Discussion Characteristic Features of the Proposed Alignment and Its Visual Representation Alignment Benchmark Determining Prediction Accuracy Experimental Setup and Results Conclusions References Polynomial Supertree Methods Revisited Introduction Methods under Consideration Simulation Study Results Conclusion References Enhancing Graph Database Indexing by Suffix Tree Structure Introduction and Related Work GraphGrepSX Preprocessing Phase Filtering and Matching Phases Experimental Results and Biological Application Conclusion References Part III: Learning Methods for Gene Expression and Mass Spectrometry Data Semi-Supervised Graph Embedding Scheme with Active Learning (SSGEAL): Classifying High Dimensional Biomedical Data Introduction Previous Work and Novel Contributions Unsupervised Dimensionality Reduction Semi-Supervised Dimensionality Reduction Active Learning Novel Contributions and Significance of SSGEAL Review of SSDR and Active Learning Methods Graph Embedding (GE) Semi-Supervised Agglomerative Graph Embedding (SSAGE) SVM-Based Active Learning to Identifying Ambiguous Samples Semi-Supervised Graph Embedding with Active Learning (SSGEAL) Initialization with Initial Embedding $Z_0$ Active Learning to Identify Ambiguous Samples X$_a$ Semi-Supervised Graph Embedding $Z_q$ Using Updated Labels Stopping Criterion Using Silhouette Index Experimental Results and Discussion Experiments and Evaluation Comparing SSGEAL with GE and SSAGE via SI and AUC Concluding Remarks References Iterated Local Search for Biclustering of Microarray Data Introduction The BILS Algorithm Iterated Local Search Preprocessing Step: Construction of the Behavior Matrix Initial Solutions and Basic Search Process Solution Representation and Search Space Evaluation Function Move and Neighborhood The General BILS Procedure Experimental Results Dataset and Experimental Protocol Statistical and Biological Significance Evaluation Conclusion and Future Work References Biologically-aware Latent Dirichlet Allocation (BaLDA) for the Classification of Expression Microarray Introduction Background Topic Models Latent Dirichlet Allocation Topics Models in Bioinformatics Biologically-aware Latent Dirichlet Allocation (BaLDA) BaLDA Inference and Learning Expression Microarray Samples Classification Experiments Conclusions References Measuring the Quality of Shifting and Scaling Patterns in Biclusters Introduction Behavioural Patterns in Gene Expression Data Transposed Virtual Error Analysis Discussion Conclusions References Frequent Episode Mining to Support Pattern Analysis in Developmental Biology Introduction Materials and Methods Finding the Episodes Episodes in Heterochrony Analysis Clustering of Developmental Profiles Results Artificial Data Sequences of Morphological Characters in Development Relative Timescale in Development Sequences of Gene Expression in Development Conclusions and Discussion References Time Series Gene Expression Data Classification via $L_1$-norm Temporal SVM Introduction Time Series Classification and Warping Distance $L_1$-norm Temporal Support Vector Machines Computational Experiments Conclusions and Future Extensions References Part IV: Bioimaging Sub-grid and Spot Detection in DNA Microarray Images Using Optimal Multi-level Thresholding Introduction The Proposed Gridding Method Optimal Multilevel Thresholding Automatic Detection of the Number of Sub-grids and Spots Experimental Results Conclusions References Quantification of Cytoskeletal Protein Localization from High-Content Images Introduction Method Cell Segmentation Intensity Transformation of Subcellular Compartments Protein Segmentation Colocalization Protein Localization Profiling Experiments and Results Sample Preparation Imaging Image Processing Cell Selection Colocalization Indexing Protein Clustering Conclusions References Pattern Recognition for High Throughput Zebrafish Imaging Using Genetic Algorithm Optimization Introduction Deformable Template Slice Representation Model Deformations Energy Function Genetic Algorithm Representation of Individuals Evaluation Selection Crossover Mutation Multiple Object Recognition Experiments Testing with Synthetic Images Testing with Zebrafish Images Conclusions and Discussion References Consensus of Ambiguity: Theory and Application of Active Learning for Biomedical Image Analysis Introduction Using Consensus Methods for Certainty and Ambiguity Active Learning for Cost-Effective Training Current Active Learning Approaches Novel Contributions of This Paper Theory of CoA Active Learning Strategy Overview Consensus of Ambiguity: Definition and Properties Experimental Setup Overview of Datasets Comparison of AL Methods Probabilistic Boosting Tree Classification Algorithm Results and Discussion Concluding Remarks References Semi-supervised Learning of Sparse Linear Models in Mass Spectral Imaging Introduction Notation and Preliminaries Structure Encoding via the Graph Laplacian Encoding Ordered Variables Encoding Prior Spatial Information Experimental Results Data Set Numerical Results Visualization Conclusion References Part V: Molecular Structure Prediction A Matrix Algorithm for RNA Secondary Structure Prediction Introduction RNA Secondary Structures MARSs Overview Matrices and Folding Base Pairing - Symmetric Fold Base Pairing - Asymmetric Fold Level 2 Folding MARSs Complexity Analysis Results Accuracy Measures Accuracy of MARSs Parallelization of MARSs Conclusion References Exploiting Long-Range Dependencies in Protein β-Sheet Secondary Structure Prediction Introduction Materials and Methods Kernel Classifiers Feature Extraction Data Sets and Experiment Setup Results and Discussion Conclusion and Future Work References Alpha Helix Prediction Based on Evolutionary Computation Introduction Our Proposal Encoding Fitness Function Genetic Operators Experiments and Discussion Conclusions and Future Work References An On/Off Lattice Approach to Protein Structure Prediction from Contact Maps Introduction Related Work Method 3Distill REMC-HPPFP On/Off Lattice Cascade Experiments Selection of the Lattice Energy Function Behavior over Time Discussion Conclusions References Part VI: Protein Protein Interaction and Network Inference Biological Protein-Protein Interaction Prediction Using Binding Free Energies and Linear Dimensionality Reduction Introduction Linear Dimensionality Reduction Other Classifiers Protein-Protein Interaction Classification Experimental Results Conclusion References Employing Publically Available Biological Expert Knowledge from Protein-Protein Interaction Information Introduction: Challenges Confronting Genome-Wide Genetic Analysis Materials and Methods STRING Interaction Scenario Simulation Metrics Evaluating Metrics Bladder Cancer Data Results Discussion Conclusion References SFFS-MR: A Floating Search Strategy for GRNs Inference Introduction GRN Inference Feature Selection Sequential Forward Selection (SFS) Sequential Forward Floating Selection (SFFS) Intrinsically Multivariate Prediction SFFS with Multiple Roots (SFFS-MR) Experimental Results Conclusion References Revisiting the Voronoi Description of Protein-Protein Interfaces: Algorithms Introduction On Classical Protein - Protein Interface Models The Voronoi Interface Bicolor Voronoi Interfaces Bicolor Interface and Interface Neighbors Topology of Bicolor Voronoi Interfaces Computing Bicolor Interfaces and Their Boundaries Geometry of Connected Components On the Geometry of Interface Facets Tricolor Interfaces and Water Molecules The $AW-BW$ Interface The $ABW$ Interface Shelling the $ABW$ Interface Conclusion and Outlook References MC$^4$: A Tempering Algorithm for Large-Sample Network Inference Introduction Methods Monte Carlo Schemes Simulation Set-Up Measuring Convergence Results Simulation Results Real Data Results Conclusions References Flow-Based Bayesian Estimation of Nonlinear Differential Equations for Modeling Biological Networks Introduction Context Strategy The Initial Condition Learning Problem Flow of an ODE and Statistical Modeling Flow-Based Bayesian Estimation Posterior Probability Estimation Using Population Monte Carlo Adaptive Importance Sampling and Population Monte-Carlo Algorithm Markovian Transition and Adaptive Kernels Experimental Results and Discussion α-pinene An Example of a Partially Observed System: The Repressilator Network in $E. coli$ Conclusion and Perspective References Author Index