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.Costas S. Iliopoulos, PhD, is Professor of AlgorithmDesign at King's College London, UK. Dr. Iliopoulos co-authored over 300 peer-reviewed articles in pattern matching and combinatorics of strings. He serves on the editorial board of the Journal of Discrete Algorithms, Computer Mathematics & Combinatorial Computing, and System Biology & Biomedical Technologies.Jason T. L. Wang, PhD, is Professor of Computer Science at the New Jersey Institute of Technology, USA. Dr. Wang has published extensively on Data Mining and Computational Molecular Biology, and has been a member of program committees for over 200 conferences and workshops in these and related areas.Albert Y. Zomaya, PhD, is the Chair Professor of High Performance Computing & Networking in the School of Information Technologies, University of Sydney, Australia. Dr. Zomaya published more than 500 scientific papers and articles and is author, co-author or editor of more than 20 books. Dr. Zomaya is Fellow of AAAS, IEEE, and IET.

• LIST OF CONTRIBUTORS xxiPREFACE xxviiI PATTERN RECOGNITION IN SEQUENCES 11 COMBINATORIAL HAPLOTYPING PROBLEMS 3Giuseppe Lancia1.1 Introduction / 31.2 Single Individual Haplotyping / 51.2.1 The Minimum Error Correction Model / 81.2.2 Probabilistic Approaches and Alternative Models / 101.3 Population Haplotyping / 121.3.1 Clark’s Rule / 141.3.2 Pure Parsimony / 151.3.3 Perfect Phylogeny / 191.3.4 Disease Association / 211.3.5 Other Models / 22References / 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.2.1 Average Length of Optimal Barcodes / 332.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.4.1 Reductions from Set Covering Problem / 362.4.2 Reduction from Graph-Coloring Problem / 382.5 Heuristic Algorithms for String Barcoding Problems / 392.5.1 Entropy-Based Method with a Different Measure for Information Content / 392.5.2 Balanced Partitioning Approach / 402.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.2.1 Background on Whole-Genome Comparison / 443.2.2 Alignment-Free Methods / 453.2.3 Average Common Subword / 463.2.4 Kullback–Leibler Information Divergence / 473.3 Underlying Approach / 473.3.1 Irredundant Common Subwords / 483.3.2 Underlying Subwords / 493.3.3 Efficient Computation of Underlying Subwords / 503.3.4 Extension to Inversions and Complements / 533.3.5 A Distance-Like Measure Based on Underlying Subwords / 533.4 Experimental Results / 543.4.1 Genome Data sets and Reference Taxonomies / 543.4.2 Whole-Genome Phylogeny Reconstruction / 563.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.2.1 Overall Objective Function / 674.2.2 Maximum Likelihood Model / 684.3 Motif Finding Algorithms / 704.3.1 DEM Motif Algorithm / 704.3.2 WEM Motif Finding Algorithm / 704.3.3 Metropolis Motif Finding Algorithm / 724.3.4 Gibbs Motif Finding Algorithm / 734.3.5 Pseudo-Gibbs Motif Finding Algorithm / 744.4 Time Complexity / 754.5 Case Studies / 754.5.1 Performance Evaluation / 764.5.2 CRP Binding Sites / 764.5.3 Multiple Motifs in Helix–Turn–Helix Protein Structure / 784.6 Conclusion / 80References / 815 GLOBAL SEQUENCE ALIGNMENT WITH A BOUNDED NUMBER OF GAPS 83Carl Barton, Tomáš 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.2.1 Chou–Fasman / 1036.2.2 GOR / 1046.2.3 PHD / 1046.2.4 PSIPRED / 1046.2.5 SPINE-X / 1056.2.6 PSSpred / 1056.2.7 Meta Methods / 1056.3 Evaluation of Protein Secondary Structure Prediction Methods / 1066.3.1 Measures / 1066.3.2 Benchmark / 1066.3.3 Performances / 1076.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.3.1 Base Classifiers / 1177.3.2 Ensemble Methods / 1187.3.3 Convex Combination / 1197.4 Postprocessing with A Generative Model / 1197.5 Dedication to Protein Secondary Structure Prediction / 1207.5.1 Biological Problem / 1217.5.2 MSVMpred2 / 1217.5.3 Hidden Semi-Markov Model / 1227.5.4 Experimental Results / 1227.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.2.1 Hierarchy of Protein Structures / 1308.2.2 Secondary Structure Elements / 1318.2.3 Structural Motifs / 1328.2.4 Available Sources for Protein Data / 1348.3 State of the Art / 1358.3.1 Protein Structure Motif Search / 1358.3.2 Promotif / 1368.3.3 Secondary-Structure Matching / 1378.3.4 Multiple Structural Alignment by Secondary Structures / 1388.4 A Novel Geometrical Approach to Motif Retrieval / 1388.4.1 Secondary Structures Cooccurrences / 1388.4.2 Cross Motif Search / 1438.4.3 Complete Cross Motif Search / 1468.5 Implementation Notes / 1498.5.1 Optimizations / 1498.5.2 Parallel Approaches / 1508.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.2.1 Noncoding RNAs and Their Secondary Structures / 1569.2.2 Pseudoknotted ncRNA Search Tools / 1579.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.2.1 Parsing Protein 3D-Structures into Graphs / 16910.3 Graph Mining / 17210.4 Subgraph Mining / 17310.5 Frequent Subgraph Discovery / 17310.5.1 Problem Definition / 17410.5.2 Candidates Generation / 17610.5.3 Frequent Subgraph Discovery Approaches / 17710.5.4 Variants of Frequent Subgraph Mining: Closed and Maximal Subgraphs / 17810.6 Feature Selection / 17910.6.1 Relevance of a Feature / 17910.7 Feature Selection for Subgraphs / 18010.7.1 Problem Statement / 18010.7.2 Mining Top-k Subgraphs / 18010.7.3 Clustering-Based Subgraph Selection / 18110.7.4 Sampling-Based Approaches / 18110.7.5 Approximate Subgraph Mining / 18110.7.6 Discriminative Subgraph Selection / 18210.7.7 Other Significant Subgraph Selection Approaches / 18210.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.2.1 GA Model Selection in Protein Structure Prediction / 19611.2.2 Common Methodology / 19811.3 Supervised Machine Learning Algorithm / 20111.3.1 Artificial Neural Networks / 20111.3.2 ANNs in Protein Structure Prediction / 20211.3.3 Support Vector Machines / 20311.4 Fuzzy Application / 20411.4.1 Fuzzy Logic / 20411.4.2 Fuzzy SVMs / 20411.4.3 Adaptive-Network-Based Fuzzy Inference Systems / 20511.4.4 Fuzzy Decision Trees / 20611.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.5.1 DomCut / 21612.5.2 Scooby-Domain / 21712.5.3 FIEFDom / 21812.5.4 Chatterjee et al. (2009) / 21912.5.5 Drop / 21912.6 Domain Boundary Prediction Using Enhanced General Regression Network / 22012.6.1 Multi-Domain Benchmark Data Set / 22012.6.2 Compact Domain Profile / 22112.6.3 The Enhanced Semi-Parametric Model / 22212.6.4 Training, Testing, and Validation / 22512.6.5 Experimental Results / 22612.7 Inter-Domain Linkers Prediction Using Compositional Index and Simulated Annealing / 22712.7.1 Compositional Index / 22812.7.2 Detecting the Optimal Set of Threshold Values Using Simulated Annealing / 22912.7.3 Experimental Results / 23012.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.2.1 Evolutionary Data Set Construction / 23813.2.2 Protein Secondary Structure Information / 23913.2.3 Method I: Intelligent Voting / 23913.2.4 Method II: Randomized Meta-Learning / 24113.2.5 Model Validation and Testing / 24213.2.6 Parameter Tuning / 24213.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.2.1 Secondary Structure Prediction / 25514.2.2 Modeling of Tertiary Structure / 25614.3 Template-Based Predictions / 25714.3.1 Homology Modeling / 25714.3.2 Threading Methods / 25714.3.3 Ab initio Modeling / 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.2.1 Graph Model for Proteins / 27015.3 Measuring Structural Similarity VIA MCES / 27215.3.1 Problem Formulation / 27315.3.2 Constructing P-Graphs / 27415.3.3 Constructing Line Graphs / 27615.3.4 Constructing Modular Graphs / 27615.3.5 Maximum Clique Detection / 27715.3.6 Experimental Results / 27715.4 Protein Comparison VIA Graph Spectra / 27915.4.1 Graph Spectra / 27915.4.2 Matrix Selection / 28115.4.3 Graph Cospectrality and Similarity / 28315.4.4 Cospectral Comparison / 28315.4.5 Experimental Results / 28415.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.4.1 Physicochemical Properties / 29616.4.2 Domain-Based Properties / 29816.5 Feature Selection / 29916.5.1 Filter Methods / 29916.5.2 Wrapper Methods / 30116.6 Classification / 30116.6.1 Linear Dimensionality Reduction / 30116.6.2 Support Vector Machines / 30316.6.3 k-Nearest Neighbor / 30316.6.4 Naive Bayes / 30416.7 Evaluation and Analysis / 30416.8 Results and Discussion / 30416.8.1 Analysis of the Prediction Properties / 30416.8.2 Analysis of Structural DDIs / 30716.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.2.1 Signal from Oligo DNA Array Image / 33618.2.2 Signal from Two-Color cDNA Array / 33718.3 Microarray Signal Analysis / 33718.3.1 Absolute Analysis and Replicates in Microarrays / 33818.3.2 Microarray Normalization / 33918.4 Algorithms for De Gene Selection / 33918.4.1 Within–Between DE Gene (WB-DEG) Selection Algorithm / 34018.4.2 Comparison of the WB-DEGs with Two Classical DE Gene Selection Methods on Latin Square Data / 34118.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.3.1 Applications / 34919.3.2 Microarray Technology / 35019.3.3 Microarray Workflow / 35019.4 RNA-Seq / 35119.5 Benefits and Drawbacks of RNA-Seq and Microarray Technologies / 35319.6 Gene Expression Profile Analysis / 35619.6.1 Data Definition / 35619.6.2 Data Analysis / 35719.6.3 Normalization and Background Correction / 35719.6.4 Genes Clustering / 35919.6.5 Experiment Classification / 36119.6.6 Software Tools for Gene Expression Profile Analysis / 36219.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.2.1 Similarity Measurement / 37420.2.2 Clustering / 37620.2.3 Biclustering / 37920.2.4 Types of Biclusters / 38020.2.5 Measurement of the Homogeneity / 38320.2.6 Biclustering Algorithms with Different Searching Schemes / 38720.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.1.1 Background Correction Methods / 39521.1.2 Normalization Methods / 39621.1.3 Literature Review / 39721.2 Arrow Plot / 39921.2.1 DE Genes Versus Special Genes / 39921.2.2 Definition and Properties of the ROC Curve / 40021.2.3 AUC and Degenerate ROC Curves / 40121.2.4 Overlapping Coefficient / 40221.2.5 Arrow Plot Construction / 40321.3 Significance Analysis of Microarrays / 40421.4 Correspondence Analysis / 40521.4.1 Basic Principles / 40521.4.2 Interpretation of CA Maps / 40621.5 Impact of the Preprocessing Methods / 40721.5.1 Class Prediction Context / 40821.5.2 Class Comparison Context / 40821.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.2.1 Inferring Gene Trees / 44123.2.2 Inferring Species Trees / 44223.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áš 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.5.1 Preprocessing / 46724.5.2 Computing Lowest Common Ancestors / 46824.5.3 Constructing the Induced Tree / 46824.5.4 Final Remarks / 47124.6 Implementation / 47324.6.1 Preprocessing / 47324.6.2 Reconstruction / 47324.6.3 Extracting Bipartitions / 47424.7 Evaluation / 47424.7.1 Test Data Sets / 47424.7.2 Experimental Results / 47524.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.2.1 Clustering Using Variability Functions / 48525.2.2 Other Variants of Clustering Functions Implemented in the Algorithm / 48725.2.3 Description of the New Algorithm / 48825.2.4 Time Complexity / 49125.3 Experimental Study / 49125.3.1 Implementation / 49125.3.2 Synthetic Data / 49125.3.3 Real Prokaryotic (Genomic) Data / 49525.4 Results and Discussion / 50125.4.1 Analysis of Synthetic Data / 50125.4.2 Analysis of Prokaryotic Data / 50225.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.4.1 Notations / 52927.4.2 Sparse Regression and the LASSO / 53027.4.3 Bayesian Regression / 53027.4.4 Evaluation Metric / 53127.5 Learning Gene Regulation Networks / 53227.5.1 Nonhomogeneous Bayesian Regression / 53327.5.2 Gradient Estimation / 53427.5.3 Simulated Bio-PEPA Data / 53427.5.4 Real mRNA Expression Profile Data / 53527.5.5 Method Evaluation and Learned Networks / 53627.6 Learning Species Interaction Networks / 54027.6.1 Regression Model of Species interactions / 54027.6.2 Multiple Global Change-Points / 54127.6.3 Mondrian Process Change-Points / 54227.6.4 Synthetic Data / 54427.6.5 Simulated Population Dynamics / 54427.6.6 Real World Plant Data / 54627.6.7 Method Evaluation and Learned Networks / 54627.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.2.1 Basics / 55728.2.2 Structure and Signaling of TLRs / 55828.2.3 TLR Signaling in Chronic Lymphocytic Leukemia / 55928.3 Structural Equation Modeling / 56028.3.1 Methodology of SEM Modeling / 56028.3.2 Assumptions / 56128.3.3 Estimation Methods / 56228.3.4 Missing Data / 56228.3.5 Goodness-of-Fit Indices / 56328.3.6 Other Indications of a Misspecified Model / 56528.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.3.1 The Algorithm / 59129.4 Experimental Setup / 59229.4.1 Data sets / 59229.4.2 Comparative Methods / 59329.4.3 Experimental Protocol / 59429.4.4 Evaluation Criteria / 59429.5 Experimental Analysis / 59629.5.1 Replenishing Missing Functions / 59629.5.2 Predicting Unlabeled Proteins / 60029.5.3 Component Analysis / 60429.5.4 Run Time Analysis / 60429.6 Conclusions / 605Acknowledgments / 606References / 606INDEX 609