Pattern Recognition in Computational Molecular Biology: Techniques and Approaches

Content: LIST OF CONTRIBUTORS xxi     PREFACE xxvii     I PATTERN RECOGNITION IN SEQUENCES 1     1 COMBINATORIAL HAPLOTYPING PROBLEMS 3 Giuseppe Lancia     1.1 Introduction / 3     1.2 Single Individual Haplotyping / 5     1.2.1 The Minimum Error Correction Model / 8     1.2.2 Probabilistic Approaches and Alternative Models / 10     1.3 Population Haplotyping / 12     1.3.1 Clark   s Rule / 14     1.3.2 Pure Parsimony / 15     1.3.3 Perfect Phylogeny / 19     1.3.4 Disease Association / 21     1.3.5 Other Models / 22     References / 23     2 ALGORITHMIC PERSPECTIVES OF THE STRING BARCODING PROBLEMS 28 Sima Behpour and Bhaskar DasGupta     2.1 Introduction / 28     2.2 Summary of Algorithmic Complexity Results for Barcoding Problems / 32     2.2.1 Average Length of Optimal Barcodes / 33     2.3 Entropy-Based Information Content Technique for Designing     Approximation Algorithms for String Barcoding Problems / 34     2.4 Techniques for Proving Inapproximability Results for String Barcoding Problems / 36     2.4.1 Reductions from Set Covering Problem / 36     2.4.2 Reduction from Graph-Coloring Problem / 38     2.5 Heuristic Algorithms for String Barcoding Problems / 39     2.5.1 Entropy-Based Method with a Different Measure for Information Content / 39     2.5.2 Balanced Partitioning Approach / 40     2.6 Conclusion / 40     Acknowledgments / 41     References / 41     3 ALIGNMENT-FREE MEASURES FOR WHOLE-GENOME COMPARISON 43 Matteo Comin and Davide Verzotto     3.1 Introduction / 43     3.2 Whole-Genome Sequence Analysis / 44     3.2.1 Background on Whole-Genome Comparison / 44     3.2.2 Alignment-Free Methods / 45     3.2.3 Average Common Subword / 46     3.2.4 Kullback   Leibler Information Divergence / 47     3.3 Underlying Approach / 47     3.3.1 Irredundant Common Subwords / 48     3.3.2 Underlying Subwords / 49     3.3.3 Efficient Computation of Underlying Subwords / 50     3.3.4 Extension to Inversions and Complements / 53     3.3.5 A Distance-Like Measure Based on Underlying Subwords / 53     3.4 Experimental Results / 54     3.4.1 Genome Data sets and Reference Taxonomies / 54     3.4.2 Whole-Genome Phylogeny Reconstruction / 56     3.5 Conclusion / 61     Author   s Contributions / 62     Acknowledgments / 62     References / 62     4 A MAXIMUM LIKELIHOOD FRAMEWORK FOR MULTIPLE SEQUENCE LOCAL ALIGNMENT 65 Chengpeng Bi     4.1 Introduction / 65     4.2 Multiple Sequence Local Alignment / 67     4.2.1 Overall Objective Function / 67     4.2.2 Maximum Likelihood Model / 68     4.3 Motif Finding Algorithms / 70     4.3.1 DEM Motif Algorithm / 70     4.3.2 WEM Motif Finding Algorithm / 70     4.3.3 Metropolis Motif Finding Algorithm / 72     4.3.4 Gibbs Motif Finding Algorithm / 73     4.3.5 Pseudo-Gibbs Motif Finding Algorithm / 74     4.4 Time Complexity / 75     4.5 Case Studies / 75     4.5.1 Performance Evaluation / 76     4.5.2 CRP Binding Sites / 76     4.5.3 Multiple Motifs in Helix   Turn   Helix Protein Structure / 78     4.6 Conclusion / 80     References / 81     5 GLOBAL SEQUENCE ALIGNMENT WITH A BOUNDED NUMBER OF GAPS 83 Carl Barton, Toma   Flouri, Costas S. Iliopoulos, and Solon P. Pissis     5.1 Introduction / 83     5.2 Definitions and Notation / 85     5.3 Problem Definition / 87     5.4 Algorithms / 88     5.5 Conclusion / 94     References / 95     II PATTERN RECOGNITION IN SECONDARY STRUCTURES 97     6 A SHORT REVIEW ON PROTEIN SECONDARY STRUCTURE PREDICTION METHODS 99 Renxiang Yan, Jiangning Song, Weiwen Cai, and Ziding Zhang     6.1 Introduction / 99     6.2 Representative Protein Secondary Structure Prediction Methods / 102     6.2.1 Chou   Fasman / 103     6.2.2 GOR / 104     6.2.3 PHD / 104     6.2.4 PSIPRED / 104     6.2.5 SPINE-X / 105     6.2.6 PSSpred / 105     6.2.7 Meta Methods / 105     6.3 Evaluation of Protein Secondary Structure Prediction Methods / 106     6.3.1 Measures / 106     6.3.2 Benchmark / 106     6.3.3 Performances / 107     6.4 Conclusion / 110     Acknowledgments / 110     References / 111     7 A GENERIC APPROACH TO BIOLOGICAL SEQUENCE SEGMENTATION PROBLEMS: APPLICATION TO PROTEIN SECONDARY STRUCTURE PREDICTION 114 Yann Guermeur and Fabien Lauer     7.1 Introduction / 114     7.2 Biological Sequence Segmentation / 115     7.3 MSVMpred / 117     7.3.1 Base Classifiers / 117     7.3.2 Ensemble Methods / 118     7.3.3 Convex Combination / 119     7.4 Postprocessing with A Generative Model / 119     7.5 Dedication to Protein Secondary Structure Prediction / 120     7.5.1 Biological Problem / 121     7.5.2 MSVMpred2 / 121     7.5.3 Hidden Semi-Markov Model / 122     7.5.4 Experimental Results / 122     7.6 Conclusions and Ongoing Research / 125     Acknowledgments / 126     References / 126     8 STRUCTURAL MOTIF IDENTIFICATION AND RETRIEVAL: A GEOMETRICAL APPROACH 129 Virginio Cantoni, Marco Ferretti, Mirto Musci, and Nahumi Nugrahaningsih     8.1 Introduction / 129     8.2 A Few Basic Concepts / 130     8.2.1 Hierarchy of Protein Structures / 130     8.2.2 Secondary Structure Elements / 131     8.2.3 Structural Motifs / 132     8.2.4 Available Sources for Protein Data / 134     8.3 State of the Art / 135     8.3.1 Protein Structure Motif Search / 135     8.3.2 Promotif / 136     8.3.3 Secondary-Structure Matching / 137     8.3.4 Multiple Structural Alignment by Secondary Structures / 138     8.4 A Novel Geometrical Approach to Motif Retrieval / 138     8.4.1 Secondary Structures Cooccurrences / 138     8.4.2 Cross Motif Search / 143     8.4.3 Complete Cross Motif Search / 146     8.5 Implementation Notes / 149     8.5.1 Optimizations / 149     8.5.2 Parallel Approaches / 150     8.6 Conclusions and Future Work / 151     Acknowledgment / 152     References / 152     9 GENOME-WIDE SEARCH FOR PSEUDOKNOTTED NONCODING RNAs: A COMPARATIVE STUDY 155 Meghana Vasavada, Kevin Byron, Yang Song, and Jason T.L. Wang     9.1 Introduction / 155     9.2 Background / 156     9.2.1 Noncoding RNAs and Their Secondary Structures / 156     9.2.2 Pseudoknotted ncRNA Search Tools / 157     9.3 Methodology / 157     9.4 Results and Interpretation / 161     9.5 Conclusion / 162     References / 163     III PATTERN RECOGNITION IN TERTIARY STRUCTURES 165     10 MOTIF DISCOVERY IN PROTEIN 3D-STRUCTURES USING GRAPH MINING TECHNIQUES 167 Wajdi Dhifli and Engelbert Mephu Nguifo     10.1 Introduction / 167     10.2 From Protein 3D-Structures to Protein Graphs / 169     10.2.1 Parsing Protein 3D-Structures into Graphs / 169     10.3 Graph Mining / 172     10.4 Subgraph Mining / 173     10.5 Frequent Subgraph Discovery / 173     10.5.1 Problem Definition / 174     10.5.2 Candidates Generation / 176     10.5.3 Frequent Subgraph Discovery Approaches / 177     10.5.4 Variants of Frequent Subgraph Mining: Closed and Maximal Subgraphs / 178     10.6 Feature Selection / 179     10.6.1 Relevance of a Feature / 179     10.7 Feature Selection for Subgraphs / 180     10.7.1 Problem Statement / 180     10.7.2 Mining Top-k Subgraphs / 180     10.7.3 Clustering-Based Subgraph Selection / 181     10.7.4 Sampling-Based Approaches / 181     10.7.5 Approximate Subgraph Mining / 181     10.7.6 Discriminative Subgraph Selection / 182     10.7.7 Other Significant Subgraph Selection Approaches / 182     10.8 Discussion / 183     10.9 Conclusion / 185     Acknowledgments / 185     References / 186     11 FUZZY AND UNCERTAIN LEARNING TECHNIQUES FOR THE ANALYSIS AND PREDICTION OF PROTEIN TERTIARY STRUCTURES 190 Chinua Umoja, Xiaxia Yu, and Robert Harrison     11.1 Introduction / 190     11.2 Genetic Algorithms / 192     11.2.1 GA Model Selection in Protein Structure Prediction / 196     11.2.2 Common Methodology / 198     11.3 Supervised Machine Learning Algorithm / 201     11.3.1 Artificial Neural Networks / 201     11.3.2 ANNs in Protein Structure Prediction / 202     11.3.3 Support Vector Machines / 203     11.4 Fuzzy Application / 204     11.4.1 Fuzzy Logic / 204     11.4.2 Fuzzy SVMs / 204     11.4.3 Adaptive-Network-Based Fuzzy Inference Systems / 205     11.4.4 Fuzzy Decision Trees / 206     11.5 Conclusion / 207     References / 208     12 PROTEIN INTER-DOMAIN LINKER PREDICTION 212 Maad Shatnawi, Paul D. Yoo, and Sami Muhaidat     12.1 Introduction / 212     12.2 Protein Structure Overview / 213     12.3 Technical Challenges and Open Issues / 214     12.4 Prediction Assessment / 215     12.5 Current Approaches / 216     12.5.1 DomCut / 216     12.5.2 Scooby-Domain / 217     12.5.3 FIEFDom / 218     12.5.4 Chatterjee et al. (2009) / 219     12.5.5 Drop / 219     12.6 Domain Boundary Prediction Using Enhanced General Regression Network / 220     12.6.1 Multi-Domain Benchmark Data Set / 220     12.6.2 Compact Domain Profile / 221     12.6.3 The Enhanced Semi-Parametric Model / 222     12.6.4 Training, Testing, and Validation / 225     12.6.5 Experimental Results / 226     12.7 Inter-Domain Linkers Prediction Using Compositional Index and Simulated Annealing / 227     12.7.1 Compositional Index / 228     12.7.2 Detecting the Optimal Set of Threshold Values Using Simulated Annealing / 229     12.7.3 Experimental Results / 230     12.8 Conclusion / 232     References / 233     13 PREDICTION OF PROLINE CIS   TRANS ISOMERIZATION 236 Paul D. Yoo, Maad Shatnawi, Sami Muhaidat, Kamal Taha, and Albert Y. Zomaya     13.1 Introduction / 236     13.2 Methods / 238     13.2.1 Evolutionary Data Set Construction / 238     13.2.2 Protein Secondary Structure Information / 239     13.2.3 Method I: Intelligent Voting / 239     13.2.4 Method II: Randomized Meta-Learning / 241     13.2.5 Model Validation and Testing / 242     13.2.6 Parameter Tuning / 242     13.3 Model Evaluation and Analysis / 243     13.4 Conclusion / 245     References / 245     IV PATTERN RECOGNITION IN QUATERNARY STRUCTURES 249     14 PREDICTION OF PROTEIN QUATERNARY STRUCTURES 251 Akbar Vaseghi, Maryam Faridounnia, Soheila Shokrollahzade, Samad Jahandideh, and Kuo-Chen Chou     14.1 Introduction / 251     14.2 Protein Structure Prediction / 255     14.2.1 Secondary Structure Prediction / 255     14.2.2 Modeling of Tertiary Structure / 256     14.3 Template-Based Predictions / 257     14.3.1 Homology Modeling / 257     14.3.2 Threading Methods / 257     14.3.3 Ab initio Modeling / 257     14.4 Critical Assessment of Protein Structure Prediction / 258     14.5 Quaternary Structure Prediction / 258     14.6 Conclusion / 261     Acknowledgments / 261     References / 261     15 COMPARISON OF PROTEIN QUATERNARY STRUCTURES BY GRAPH APPROACHES 266 Sheng-Lung Peng and Yu-Wei Tsay     15.1 Introduction / 266     15.2 Similarity in the Graph Model / 268     15.2.1 Graph Model for Proteins / 270     15.3 Measuring Structural Similarity VIA MCES / 272     15.3.1 Problem Formulation / 273     15.3.2 Constructing P-Graphs / 274     15.3.3 Constructing Line Graphs / 276     15.3.4 Constructing Modular Graphs / 276     15.3.5 Maximum Clique Detection / 277     15.3.6 Experimental Results / 277     15.4 Protein Comparison VIA Graph Spectra / 279     15.4.1 Graph Spectra / 279     15.4.2 Matrix Selection / 281     15.4.3 Graph Cospectrality and Similarity / 283     15.4.4 Cospectral Comparison / 283     15.4.5 Experimental Results / 284     15.5 Conclusion / 287     References / 287     16 STRUCTURAL DOMAINS IN PREDICTION OF BIOLOGICAL PROTEIN   PROTEIN INTERACTIONS 291 Mina Maleki, Michael Hall, and Luis Rueda     16.1 Introduction / 291     16.2 Structural Domains / 293     16.3 The Prediction Framework / 293     16.4 Feature Extraction and Prediction Properties / 294     16.4.1 Physicochemical Properties / 296     16.4.2 Domain-Based Properties / 298     16.5 Feature Selection / 299     16.5.1 Filter Methods / 299     16.5.2 Wrapper Methods / 301     16.6 Classification / 301     16.6.1 Linear Dimensionality Reduction / 301     16.6.2 Support Vector Machines / 303     16.6.3 k-Nearest Neighbor / 303     16.6.4 Naive Bayes / 304     16.7 Evaluation and Analysis / 304     16.8 Results and Discussion / 304     16.8.1 Analysis of the Prediction Properties / 304     16.8.2 Analysis of Structural DDIs / 307     16.9 Conclusion / 309     References / 310     V PATTERN RECOGNITION IN MICROARRAYS 315     17 CONTENT-BASED RETRIEVAL OF MICROARRAY EXPERIMENTS 317 Hasan O gul     17.1 Introduction / 317     17.2 Information Retrieval: Terminology and Background / 318     17.3 Content-Based Retrieval / 320     17.4 Microarray Data and Databases / 322     17.5 Methods for Retrieving Microarray Experiments / 324     17.6 Similarity Metrics / 327     17.7 Evaluating Retrieval Performance / 329     17.8 Software Tools / 330     17.9 Conclusion and Future Directions / 331     Acknowledgment / 332     References / 332     18 EXTRACTION OF DIFFERENTIALLY EXPRESSED GENES IN MICROARRAY DATA 335 Tiratha Raj Singh, Brigitte Vannier, and Ahmed Moussa     18.1 Introduction / 335     18.2 From Microarray Image to Signal / 336     18.2.1 Signal from Oligo DNA Array Image / 336     18.2.2 Signal from Two-Color cDNA Array / 337     18.3 Microarray Signal Analysis / 337     18.3.1 Absolute Analysis and Replicates in Microarrays / 338     18.3.2 Microarray Normalization / 339     18.4 Algorithms for De Gene Selection / 339     18.4.1 Within   Between DE Gene (WB-DEG) Selection Algorithm / 340     18.4.2 Comparison of the WB-DEGs with Two Classical DE Gene Selection Methods on Latin Square Data / 341     18.5 Gene Ontology Enrichment and Gene Set Enrichment Analysis / 343     18.6 Conclusion / 345     References / 345     19 CLUSTERING AND CLASSIFICATION TECHNIQUES FOR GENE EXPRESSION PROFILE PATTERN ANALYSIS 347 Emanuel Weitschek, Giulia Fiscon, Valentina Fustaino, Giovanni Felici, and Paola Bertolazzi     19.1 Introduction / 347     19.2 Transcriptome Analysis / 348     19.3 Microarrays / 349     19.3.1 Applications / 349     19.3.2 Microarray Technology / 350     19.3.3 Microarray Workflow / 350     19.4 RNA-Seq / 351     19.5 Benefits and Drawbacks of RNA-Seq and Microarray Technologies / 353     19.6 Gene Expression Profile Analysis / 356     19.6.1 Data Definition / 356     19.6.2 Data Analysis / 357     19.6.3 Normalization and Background Correction / 357     19.6.4 Genes Clustering / 359     19.6.5 Experiment Classification / 361     19.6.6 Software Tools for Gene Expression Profile Analysis / 362     19.7 Real Case Studies / 364     19.8 Conclusions / 367     References / 368     20 MINING INFORMATIVE PATTERNS IN MICROARRAY DATA 371 Li Teng     20.1 Introduction / 371     20.2 Patterns with Similarity / 373     20.2.1 Similarity Measurement / 374     20.2.2 Clustering / 376     20.2.3 Biclustering / 379     20.2.4 Types of Biclusters / 380     20.2.5 Measurement of the Homogeneity / 383     20.2.6 Biclustering Algorithms with Different Searching Schemes / 387     20.3 Conclusion / 391     References / 391     21 ARROW PLOT AND CORRESPONDENCE ANALYSIS MAPS FOR VISUALIZING THE EFFECTS OF BACKGROUND CORRECTION AND NORMALIZATION METHODS ON MICROARRAY DATA 394 Carina Silva, Adelaide Freitas, Sara Roque, and Lisete Sousa     21.1 Overview / 394     21.1.1 Background Correction Methods / 395     21.1.2 Normalization Methods / 396     21.1.3 Literature Review / 397     21.2 Arrow Plot / 399     21.2.1 DE Genes Versus Special Genes / 399     21.2.2 Definition and Properties of the ROC Curve / 400     21.2.3 AUC and Degenerate ROC Curves / 401     21.2.4 Overlapping Coefficient / 402     21.2.5 Arrow Plot Construction / 403     21.3 Significance Analysis of Microarrays / 404     21.4 Correspondence Analysis / 405     21.4.1 Basic Principles / 405     21.4.2 Interpretation of CA Maps / 406     21.5 Impact of the Preprocessing Methods / 407     21.5.1 Class Prediction Context / 408     21.5.2 Class Comparison Context / 408     21.6 Conclusions / 412     Acknowledgments / 413     References / 413     VI PATTERN RECOGNITION IN PHYLOGENETIC TREES 417     22 PATTERN RECOGNITION IN PHYLOGENETICS: TREES AND NETWORKS 419 David A. Morrison     22.1 Introduction / 419     22.2 Networks and Trees / 420     22.3 Patterns and Their Processes / 424     22.4 The Types of Patterns / 427     22.5 Fingerprints / 431     22.6 Constructing Networks / 433     22.7 Multi-Labeled Trees / 435     22.8 Conclusion / 436     References / 437     23 DIVERSE CONSIDERATIONS FOR SUCCESSFUL PHYLOGENETIC TREE RECONSTRUCTION: IMPACTS FROM MODEL MISSPECIFICATION, RECOMBINATION, HOMOPLASY, AND PATTERN RECOGNITION 439 Diego Mallo, Agustin Sanchez-Cobos, and Miguel Arenas     23.1 Introduction / 440     23.2 Overview on Methods and Frameworks for Phylogenetic Tree Reconstruction / 440     23.2.1 Inferring Gene Trees / 441     23.2.2 Inferring Species Trees / 442     23.3 Influence of Substitution Model Misspecification on Phylogenetic Tree Reconstruction / 445     23.4 Influence of Recombination on Phylogenetic Tree Reconstruction / 446     23.5 Influence of Diverse Evolutionary Processes on Species Tree Reconstruction / 447     23.6 Influence of Homoplasy on Phylogenetic Tree Reconstruction: The Goals of Pattern Recognition / 449     23.7 Concluding Remarks / 449     Acknowledgments / 450     References / 450     24 AUTOMATED PLAUSIBILITY ANALYSIS OF LARGE PHYLOGENIES 457 David Dao, Toma   Flouri, and Alexandros Stamatakis     24.1 Introduction / 457     24.2 Preliminaries / 459     24.3 A Naive Approach / 462     24.4 Toward a Faster Method / 463     24.5 Improved Algorithm / 467     24.5.1 Preprocessing / 467     24.5.2 Computing Lowest Common Ancestors / 468     24.5.3 Constructing the Induced Tree / 468     24.5.4 Final Remarks / 471     24.6 Implementation / 473     24.6.1 Preprocessing / 473     24.6.2 Reconstruction / 473     24.6.3 Extracting Bipartitions / 474     24.7 Evaluation / 474     24.7.1 Test Data Sets / 474     24.7.2 Experimental Results / 475     24.8 Conclusion / 479     Acknowledgment / 481     References / 481     25 A NEW FAST METHOD FOR DETECTING AND VALIDATING HORIZONTAL GENE TRANSFER EVENTS USING PHYLOGENETIC TREES AND AGGREGATION FUNCTIONS 483 Dunarel Badescu, Nadia Tahiri, and Vladimir Makarenkov     25.1 Introduction / 483     25.2 Methods / 485     25.2.1 Clustering Using Variability Functions / 485     25.2.2 Other Variants of Clustering Functions Implemented in the Algorithm / 487     25.2.3 Description of the New Algorithm / 488     25.2.4 Time Complexity / 491     25.3 Experimental Study / 491     25.3.1 Implementation / 491     25.3.2 Synthetic Data / 491     25.3.3 Real Prokaryotic (Genomic) Data / 495     25.4 Results and Discussion / 501     25.4.1 Analysis of Synthetic Data / 501     25.4.2 Analysis of Prokaryotic Data / 502     25.5 Conclusion / 502     References / 503     VII PATTERN RECOGNITION IN BIOLOGICAL NETWORKS 505     26 COMPUTATIONAL METHODS FOR MODELING BIOLOGICAL INTERACTION NETWORKS 507 Christos Makris and Evangelos Theodoridis     26.1 Introduction / 507     26.2 Measures/Metrics / 508     26.3 Models of Biological Networks / 511     26.4 Reconstructing and Partitioning Biological Networks / 511     26.5 PPI Networks / 513     26.6 Mining PPI Networks   Interaction Prediction / 517     26.7 Conclusions / 519     References / 519     27 BIOLOGICAL NETWORK INFERENCE AT MULTIPLE SCALES: FROM GENE REGULATION TO SPECIES INTERACTIONS 525 Andrej Aderhold, V Anne Smith, and Dirk Husmeier     27.1 Introduction / 525     27.2 Molecular Systems / 528     27.3 Ecological Systems / 528     27.4 Models and Evaluation / 529     27.4.1 Notations / 529     27.4.2 Sparse Regression and the LASSO / 530     27.4.3 Bayesian Regression / 530     27.4.4 Evaluation Metric / 531     27.5 Learning Gene Regulation Networks / 532     27.5.1 Nonhomogeneous Bayesian Regression / 533     27.5.2 Gradient Estimation / 534     27.5.3 Simulated Bio-PEPA Data / 534     27.5.4 Real mRNA Expression Profile Data / 535     27.5.5 Method Evaluation and Learned Networks / 536     27.6 Learning Species Interaction Networks / 540     27.6.1 Regression Model of Species interactions / 540     27.6.2 Multiple Global Change-Points / 541     27.6.3 Mondrian Process Change-Points / 542     27.6.4 Synthetic Data / 544     27.6.5 Simulated Population Dynamics / 544     27.6.6 Real World Plant Data / 546     27.6.7 Method Evaluation and Learned Networks / 546     27.7 Conclusion / 550     References / 550     28 DISCOVERING CAUSAL PATTERNS WITH STRUCTURAL EQUATION MODELING: APPLICATION TO TOLL-LIKE RECEPTOR SIGNALING PATHWAY IN CHRONIC LYMPHOCYTIC LEUKEMIA 555 Athina Tsanousa, Stavroula Ntoufa, Nikos Papakonstantinou, Kostas Stamatopoulos, and Lefteris Angelis     28.1 Introduction / 555     28.2 Toll-Like Receptors / 557     28.2.1 Basics / 557     28.2.2 Structure and Signaling of TLRs / 558     28.2.3 TLR Signaling in Chronic Lymphocytic Leukemia / 559     28.3 Structural Equation Modeling / 560     28.3.1 Methodology of SEM Modeling / 560     28.3.2 Assumptions / 561     28.3.3 Estimation Methods / 562     28.3.4 Missing Data / 562     28.3.5 Goodness-of-Fit Indices / 563     28.3.6 Other Indications of a Misspecified Model / 565     28.4 Application / 566     28.5 Conclusion / 580     References / 581     29 ANNOTATING PROTEINS WITH INCOMPLETE LABEL INFORMATION 585 Guoxian Yu, Huzefa Rangwala, and Carlotta Domeniconi     29.1 Introduction / 585     29.2 Related Work / 587     29.3 Problem Formulation / 589     29.3.1 The Algorithm / 591     29.4 Experimental Setup / 592     29.4.1 Data sets / 592     29.4.2 Comparative Methods / 593     29.4.3 Experimental Protocol / 594     29.4.4 Evaluation Criteria / 594     29.5 Experimental Analysis / 596     29.5.1 Replenishing Missing Functions / 596     29.5.2 Predicting Unlabeled Proteins / 600     29.5.3 Component Analysis / 604     29.5.4 Run Time Analysis / 604     29.6 Conclusions / 605     Acknowledgments / 606     References / 606     INDEX 609