Pattern Recognition in Computational Molecular Biology

Mourad Elloumi, PhD, is Professor in Computer Science at the University of Tunis-El Manar, Tunisia. Dr. Elloumi is the author/co-author of more than 50 publications in international journals and conference proceedings related to Algorithmics, Computational Molecular Biology, and Knowledge Discovery and Data Mining.

A comprehensive overview of high-performance pattern recognition techniques and approaches to Computational Molecular BiologyThis book surveys the developments of techniques and approaches on pattern recognition related to Computational Molecular Biology. Providing a broad coverage of the field, the authors cover fundamental and technical information on these techniques and approaches, as well as discussing their related problems. The text consists of twenty nine chapters, organized into seven parts: Pattern Recognition in Sequences, Pattern Recognition in Secondary Structures, Pattern Recognition in Tertiary Structures, Pattern Recognition in Quaternary Structures, Pattern Recognition in Microarrays, Pattern Recognition in Phylogenetic Trees, and Pattern Recognition in Biological Networks.* Surveys the development of techniques and approaches on pattern recognition in biomolecular data* Discusses pattern recognition in primary, secondary, tertiary and quaternary structures, as well as microarrays, phylogenetic trees and biological networks* Includes case studies and examples to further illustrate the concepts discussed in the bookPattern Recognition in Computational Molecular Biology: Techniques and Approaches is a reference for practitioners and professional researches in Computer Science, Life Science, and Mathematics. This book also serves as a supplementary reading for graduate students and young researches interested in Computational Molecular Biology.

LIST OF CONTRIBUTORS xxiPREFACE xxviiI PATTERN RECOGNITION IN SEQUENCES 11 COMBINATORIAL HAPLOTYPING PROBLEMS 3Giuseppe Lancia1.1 Introduction / 31.2 Single Individual Haplotyping / 51.3 Population Haplotyping / 12References / 232 ALGORITHMIC PERSPECTIVES OF THE STRING BARCODING PROBLEMS 28Sima Behpour and Bhaskar DasGupta2.1 Introduction / 282.2 Summary of Algorithmic Complexity Results for Barcoding Problems / 322.3 Entropy-Based Information Content Technique for DesigningApproximation Algorithms for String Barcoding Problems / 342.4 Techniques for Proving Inapproximability Results for String Barcoding Problems / 362.5 Heuristic Algorithms for String Barcoding Problems / 392.6 Conclusion / 40Acknowledgments / 41References / 413 ALIGNMENT-FREE MEASURES FOR WHOLE-GENOME COMPARISON 43Matteo Comin and Davide Verzotto3.1 Introduction / 433.2 Whole-Genome Sequence Analysis / 443.3 Underlying Approach / 473.4 Experimental Results / 543.5 Conclusion / 61Author's Contributions / 62Acknowledgments / 62References / 624 A MAXIMUM LIKELIHOOD FRAMEWORK FOR MULTIPLE SEQUENCE LOCAL ALIGNMENT 65Chengpeng Bi4.1 Introduction / 654.2 Multiple Sequence Local Alignment / 674.3 Motif Finding Algorithms / 704.4 Time Complexity / 754.5 Case Studies / 754.6 Conclusion / 80References / 815 GLOBAL SEQUENCE ALIGNMENT WITH A BOUNDED NUMBER OF GAPS 83Carl Barton, Tomás Flouri, Costas S. Iliopoulos, and Solon P. Pissis5.1 Introduction / 835.2 Definitions and Notation / 855.3 Problem Definition / 875.4 Algorithms / 885.5 Conclusion / 94References / 95II PATTERN RECOGNITION IN SECONDARY STRUCTURES 976 A SHORT REVIEW ON PROTEIN SECONDARY STRUCTURE PREDICTION METHODS 99Renxiang Yan, Jiangning Song, Weiwen Cai, and Ziding Zhang6.1 Introduction / 996.2 Representative Protein Secondary Structure Prediction Methods / 1026.3 Evaluation of Protein Secondary Structure Prediction Methods / 1066.4 Conclusion / 110Acknowledgments / 110References / 1117 A GENERIC APPROACH TO BIOLOGICAL SEQUENCE SEGMENTATION PROBLEMS: APPLICATION TO PROTEIN SECONDARY STRUCTURE PREDICTION 114Yann Guermeur and Fabien Lauer7.1 Introduction / 1147.2 Biological Sequence Segmentation / 1157.3 MSVMpred / 1177.4 Postprocessing with A Generative Model / 1197.5 Dedication to Protein Secondary Structure Prediction / 1207.6 Conclusions and Ongoing Research / 125Acknowledgments / 126References / 1268 STRUCTURAL MOTIF IDENTIFICATION AND RETRIEVAL: A GEOMETRICAL APPROACH 129Virginio Cantoni, Marco Ferretti, Mirto Musci, and Nahumi Nugrahaningsih8.1 Introduction / 1298.2 A Few Basic Concepts / 1308.3 State of the Art / 1358.4 A Novel Geometrical Approach to Motif Retrieval / 1388.5 Implementation Notes / 1498.6 Conclusions and Future Work / 151Acknowledgment / 152References / 1529 GENOME-WIDE SEARCH FOR PSEUDOKNOTTED NONCODING RNAs: A COMPARATIVE STUDY 155Meghana Vasavada, Kevin Byron, Yang Song, and Jason T.L. Wang9.1 Introduction / 1559.2 Background / 1569.3 Methodology / 1579.4 Results and Interpretation / 1619.5 Conclusion / 162References / 163III PATTERN RECOGNITION IN TERTIARY STRUCTURES 16510 MOTIF DISCOVERY IN PROTEIN 3D-STRUCTURES USING GRAPH MINING TECHNIQUES 167Wajdi Dhifli and Engelbert Mephu Nguifo10.1 Introduction / 16710.2 From Protein 3D-Structures to Protein Graphs / 16910.3 Graph Mining / 17210.4 Subgraph Mining / 17310.5 Frequent Subgraph Discovery / 17310.6 Feature Selection / 17910.7 Feature Selection for Subgraphs / 18010.8 Discussion / 18310.9 Conclusion / 185Acknowledgments / 185References / 18611 FUZZY AND UNCERTAIN LEARNING TECHNIQUES FOR THE ANALYSIS AND PREDICTION OF PROTEIN TERTIARY STRUCTURES 190Chinua Umoja, Xiaxia Yu, and Robert Harrison11.1 Introduction / 19011.2 Genetic Algorithms / 19211.3 Supervised Machine Learning Algorithm / 20111.4 Fuzzy Application / 20411.5 Conclusion / 207References / 20812 PROTEIN INTER-DOMAIN LINKER PREDICTION 212Maad Shatnawi, Paul D. Yoo, and Sami Muhaidat12.1 Introduction / 21212.2 Protein Structure Overview / 21312.3 Technical Challenges and Open Issues / 21412.4 Prediction Assessment / 21512.5 Current Approaches / 21612.6 Domain Boundary Prediction Using Enhanced General Regression Network / 22012.7 Inter-Domain Linkers Prediction Using Compositional Index and Simulated Annealing / 22712.8 Conclusion / 232References / 23313 PREDICTION OF PROLINE CIS-TRANS ISOMERIZATION 236Paul D. Yoo, Maad Shatnawi, Sami Muhaidat, Kamal Taha, and Albert Y. Zomaya13.1 Introduction / 23613.2 Methods / 23813.3 Model Evaluation and Analysis / 24313.4 Conclusion / 245References / 245IV PATTERN RECOGNITION IN QUATERNARY STRUCTURES 24914 PREDICTION OF PROTEIN QUATERNARY STRUCTURES 251Akbar Vaseghi, Maryam Faridounnia, Soheila Shokrollahzade, Samad Jahandideh, and Kuo-Chen Chou14.1 Introduction / 25114.2 Protein Structure Prediction / 25514.3 Template-Based Predictions / 25714.4 Critical Assessment of Protein Structure Prediction / 25814.5 Quaternary Structure Prediction / 25814.6 Conclusion / 261Acknowledgments / 261References / 26115 COMPARISON OF PROTEIN QUATERNARY STRUCTURES BY GRAPH APPROACHES 266Sheng-Lung Peng and Yu-Wei Tsay15.1 Introduction / 26615.2 Similarity in the Graph Model / 26815.3 Measuring Structural Similarity VIA MCES / 27215.4 Protein Comparison VIA Graph Spectra / 27915.5 Conclusion / 287References / 28716 STRUCTURAL DOMAINS IN PREDICTION OF BIOLOGICAL PROTEIN-PROTEIN INTERACTIONS 291Mina Maleki, Michael Hall, and Luis Rueda16.1 Introduction / 29116.2 Structural Domains / 29316.3 The Prediction Framework / 29316.4 Feature Extraction and Prediction Properties / 29416.5 Feature Selection / 29916.6 Classification / 30116.7 Evaluation and Analysis / 30416.8 Results and Discussion / 30416.9 Conclusion / 309References / 310V PATTERN RECOGNITION IN MICROARRAYS 31517 CONTENT-BASED RETRIEVAL OF MICROARRAY EXPERIMENTS 317Hasan O¢gul17.1 Introduction / 31717.2 Information Retrieval: Terminology and Background / 31817.3 Content-Based Retrieval / 32017.4 Microarray Data and Databases / 32217.5 Methods for Retrieving Microarray Experiments / 32417.6 Similarity Metrics / 32717.7 Evaluating Retrieval Performance / 32917.8 Software Tools / 33017.9 Conclusion and Future Directions / 331Acknowledgment / 332References / 33218 EXTRACTION OF DIFFERENTIALLY EXPRESSED GENES IN MICROARRAY DATA 335Tiratha Raj Singh, Brigitte Vannier, and Ahmed Moussa18.1 Introduction / 33518.2 From Microarray Image to Signal / 33618.3 Microarray Signal Analysis / 33718.4 Algorithms for De Gene Selection / 33918.5 Gene Ontology Enrichment and Gene Set Enrichment Analysis / 34318.6 Conclusion / 345References / 34519 CLUSTERING AND CLASSIFICATION TECHNIQUES FOR GENE EXPRESSION PROFILE PATTERN ANALYSIS 347Emanuel Weitschek, Giulia Fiscon, Valentina Fustaino, Giovanni Felici, and Paola Bertolazzi19.1 Introduction / 34719.2 Transcriptome Analysis / 34819.3 Microarrays / 34919.4 RNA-Seq / 35119.5 Benefits and Drawbacks of RNA-Seq and Microarray Technologies / 35319.6 Gene Expression Profile Analysis / 35619.7 Real Case Studies / 36419.8 Conclusions / 367References / 36820 MINING INFORMATIVE PATTERNS IN MICROARRAY DATA 371Li Teng20.1 Introduction / 37120.2 Patterns with Similarity / 37320.3 Conclusion / 391References / 39121 ARROW PLOT AND CORRESPONDENCE ANALYSIS MAPS FOR VISUALIZING THE EFFECTS OF BACKGROUND CORRECTION AND NORMALIZATION METHODS ON MICROARRAY DATA 394Carina Silva, Adelaide Freitas, Sara Roque, and Lisete Sousa21.1 Overview / 39421.2 Arrow Plot / 39921.3 Significance Analysis of Microarrays / 40421.4 Correspondence Analysis / 40521.5 Impact of the Preprocessing Methods / 40721.6 Conclusions / 412Acknowledgments / 413References / 413VI PATTERN RECOGNITION IN PHYLOGENETIC TREES 41722 PATTERN RECOGNITION IN PHYLOGENETICS: TREES AND NETWORKS 419David A. Morrison22.1 Introduction / 41922.2 Networks and Trees / 42022.3 Patterns and Their Processes / 42422.4 The Types of Patterns / 42722.5 Fingerprints / 43122.6 Constructing Networks / 43322.7 Multi-Labeled Trees / 43522.8 Conclusion / 436References / 43723 DIVERSE CONSIDERATIONS FOR SUCCESSFUL PHYLOGENETIC TREE RECONSTRUCTION: IMPACTS FROM MODEL MISSPECIFICATION, RECOMBINATION, HOMOPLASY, AND PATTERN RECOGNITION 439Diego Mallo, Agustín Sánchez-Cobos, and Miguel Arenas23.1 Introduction / 44023.2 Overview on Methods and Frameworks for Phylogenetic Tree Reconstruction / 44023.3 Influence of Substitution Model Misspecification on Phylogenetic Tree Reconstruction / 44523.4 Influence of Recombination on Phylogenetic Tree Reconstruction / 44623.5 Influence of Diverse Evolutionary Processes on Species Tree Reconstruction / 44723.6 Influence of Homoplasy on Phylogenetic Tree Reconstruction: The Goals of Pattern Recognition / 44923.7 Concluding Remarks / 449Acknowledgments / 450References / 45024 AUTOMATED PLAUSIBILITY ANALYSIS OF LARGE PHYLOGENIES 457David Dao, Tomás Flouri, and Alexandros Stamatakis24.1 Introduction / 45724.2 Preliminaries / 45924.3 A Naïve Approach / 46224.4 Toward a Faster Method / 46324.5 Improved Algorithm / 46724.6 Implementation / 47324.7 Evaluation / 47424.8 Conclusion / 479Acknowledgment / 481References / 48125 A NEW FAST METHOD FOR DETECTING AND VALIDATING HORIZONTAL GENE TRANSFER EVENTS USING PHYLOGENETIC TREES AND AGGREGATION FUNCTIONS 483Dunarel Badescu, Nadia Tahiri, and Vladimir Makarenkov25.1 Introduction / 48325.2 Methods / 48525.3 Experimental Study / 49125.4 Results and Discussion / 50125.5 Conclusion / 502References / 503VII PATTERN RECOGNITION IN BIOLOGICAL NETWORKS 50526 COMPUTATIONAL METHODS FOR MODELING BIOLOGICAL INTERACTION NETWORKS 507Christos Makris and Evangelos Theodoridis26.1 Introduction / 50726.2 Measures/Metrics / 50826.3 Models of Biological Networks / 51126.4 Reconstructing and Partitioning Biological Networks / 51126.5 PPI Networks / 51326.6 Mining PPI Networks--Interaction Prediction / 51726.7 Conclusions / 519References / 51927 BIOLOGICAL NETWORK INFERENCE AT MULTIPLE SCALES: FROM GENE REGULATION TO SPECIES INTERACTIONS 525Andrej Aderhold, V Anne Smith, and Dirk Husmeier27.1 Introduction / 52527.2 Molecular Systems / 52827.3 Ecological Systems / 52827.4 Models and Evaluation / 52927.5 Learning Gene Regulation Networks / 53227.6 Learning Species Interaction Networks / 54027.7 Conclusion / 550References / 55028 DISCOVERING CAUSAL PATTERNS WITH STRUCTURAL EQUATION MODELING: APPLICATION TO TOLL-LIKE RECEPTOR SIGNALING PATHWAY IN CHRONIC LYMPHOCYTIC LEUKEMIA 555Athina Tsanousa, Stavroula Ntoufa, Nikos Papakonstantinou, Kostas Stamatopoulos, and Lefteris Angelis28.1 Introduction / 55528.2 Toll-Like Receptors / 55728.3 Structural Equation Modeling / 56028.4 Application / 56628.5 Conclusion / 580References / 58129 ANNOTATING PROTEINS WITH INCOMPLETE LABEL INFORMATION 585Guoxian Yu, Huzefa Rangwala, and Carlotta Domeniconi29.1 Introduction / 58529.2 Related Work / 58729.3 Problem Formulation / 58929.4 Experimental Setup / 59229.5 Experimental Analysis / 59629.6 Conclusions / 605Acknowledgments / 606References / 606INDEX 609