Multiobjective Optimization Algorithms for Bioinformatics

This book provides an updated and in-depth introduction to the application of multiobjective optimization techniques in bioinformatics. In particular, it presents multiobjective solutions to a range of complex real-world bioinformatics problems. The authors first provide a comprehensive yet concise and self-contained introduction to relevant preliminary methodical constructions such as genetic algorithms, multiobjective optimization, data mining and several challenges in the bioinformatics domain. This is followed by several systematic applications of these techniques to real-world bioinformatics problems in the areas of gene expression and network biology. The book also features detailed theoretical and mathematical notes to facilitate reader comprehension. The book offers a valuable asset for a broad range of readers – from undergraduate to postgraduate, and as a textbook or reference work. Researchers and professionals can use the book not only to enrich their knowledge of multiobjective optimization and bioinformatics, but also as a comprehensive reference guide to applying and devising novel methods in bioinformatics and related domains. Preface Contents 1 Introduction 1.1 Concepts of Multiobjective Optimization 1.2 MOO in Data Mining and Machine Learning 1.2.1 Multiobjective Optimization in Clustering 1.2.2 Multiobjective Optimization in Classification 1.2.3 Multiobjective Optimization in Feature Selection 1.2.4 Multiobjective Optimization in AssociationRule Mining 1.2.5 Multiobjective Optimization in Other Data Mining Tasks 1.3 Multiobjective Optimization for Bioinformatics Tasks 1.3.1 Gene Expression Analysis 1.3.2 Gene Clustering 1.3.3 Coexpression Clustering 1.3.4 Gene and MicroRNA Marker Detection 1.3.5 Module Detection in Biological Networks 1.4 Summary and Scope of the Book 2 Multiobjective Interactive Fuzzy Clustering for Gene Expression Data 2.1 Clustering and Validity Indices 2.1.1 Fuzzy C-means Clustering 2.1.2 Hierarchical Clustering 2.1.3 Cluster Validity Indices 2.1.3.1 Davies-Bouldin Index 2.1.3.2 Xie-Beni Index 2.1.3.3 Jm Index 2.1.3.4 PBM Index 2.1.3.5 Silhouette Index 2.2 Multiobjective Fuzzy Clustering 2.2.1 NSGA-II Algorithm 2.2.2 Multiobjective Clustering 2.3 Interactive Multiobjective Fuzzy Clustering (IMOC) 2.4 Experimental Results 2.4.1 Datasets for Experiments 2.4.1.1 Human Fibroblasts Serum Dataset 2.4.1.2 Yeast Cell Cycle 2.4.2 Performance Measures 2.4.3 Input Parameters 2.4.4 Results and Discussion 2.4.5 Statistical Significance Test 2.5 Summary 3 Multiobjective Rank Aggregation for Gene Prioritization 3.1 Introduction 3.2 Rank Aggregation Techniques 3.2.1 MC4 Algorithm 3.2.2 MCT Algorithm 3.2.3 Robust Rank Aggregation 3.2.4 Condorcet Ranking 3.2.5 Rank Aggregation by Voting 3.3 Distance Metrics for Ranking 3.3.1 Kendall's Tau Distance (τ) 3.3.2 Spearman's Footrule Distance (ρ) 3.4 Objective Functions for Multiobjective Rank Aggregation 3.5 Multiobjective PSO-based Rank Aggregation 3.5.1 Encoding Mechanism of a Particle 3.5.2 Initialization 3.5.3 Computing the Fitness Values 3.5.4 Updating the Position and Velocity 3.5.5 Updating the Non-dominated Archive 3.5.6 Overall Algorithm 3.6 Experimental Results 3.6.1 Datasets and Preprocessing 3.6.1.1 Artificial Datasets 3.6.1.2 Real-Life Datasets 3.6.1.3 Preprocessing of the Datasets 3.6.2 Results and Discussion 3.6.2.1 Results for Artificial Datasets 3.6.2.2 Results for Real-Life Datasets 3.7 Summary 4 Multiobjective Simultaneous Gene Ranking and Clustering 4.1 Introduction 4.2 Multiobjective Simultaneous Clustering and Gene Ranking 4.2.1 Chromosome Representation and Initial Population 4.2.2 Fitness Computation 4.2.3 Crossover and Mutation 4.2.4 Selection, Elitism, and Termination 4.2.5 Final Solution Selection 4.3 Experimental Results 4.3.1 Experimental Design 4.3.1.1 Artificial Datasets 4.3.1.2 Real-life Datasets 4.3.1.3 Parameter Settings 4.3.1.4 Performance Measures 4.3.1.5 Competitive Methods 4.3.2 Result and Discussion 4.4 Summary 5 Multiobjective Feature Selection for Identifying MicroRNA Markers 5.1 Introduction 5.2 Multiobjective Feature Selection 5.2.1 Encoding Scheme and Initialization 5.2.2 Computing the Objectives 5.2.3 Reproduction Using Selection, Crossover, and Mutation 5.2.4 Maintaining an Archive 5.2.5 Selecting the Final Solution 5.3 Experimental Results 5.3.1 Comparative Methods 5.3.2 Datasets and Preprocessing 5.3.3 Evaluation Metrics 5.3.4 Results and Discussion 5.4 Summary 6 Multiobjective Approach to Detection of Differentially Coexpressed Modules 6.1 Introduction 6.2 DiffCoMO: Differential Coexpressed Module Detection 6.2.1 Differential Coexpression of Gene in Two Phenotypes 6.2.2 The DiffCoMO Framework 6.2.2.1 Objective Functions 6.2.3 Evaluating Objective Functions 6.3 Experimental Results 6.3.1 Description of Dataset 6.3.2 Comparing DiffCoMO with Some State of the Art 6.3.3 Statistical Significance of Identified Modules 6.3.4 Performance on a Simulated Dataset 6.3.5 Biological Validation of Modules 6.3.5.1 GO and Pathway Enrichment 6.3.5.2 miRNA Enrichment 6.3.6 Performance of DiffCoMO in Expression Data with Large Samples 6.4 Summary 7 Multiobjective Approach to Cancer-Associated MicroRNA Module Detection 7.1 Introduction 7.2 Construction of Differential Coexpression Network 7.3 Semantic Similarity Measure for MicroRNA Pairs 7.4 Multiobjective Module Detection 7.4.1 Chromosome Encoding 7.4.2 Computation of Objective Functions 7.4.3 Process of Obtaining Non-dominated Solutions 7.4.4 Obtaining the miRNA Subset from the Non-dominated Solutions 7.5 Experimental Results 7.5.1 Dataset Details and Preprocessing 7.5.2 Parameter Setting 7.5.3 Results 7.5.4 Statistical Significance of the Identified Module 7.5.5 Comparison with State-of-the-Art Algorithms 7.5.6 Biological Relevance Study 7.6 Summary 8 Multiobjective Approach to Prediction of Protein Subcellular Locations 8.1 Introduction 8.2 Feature Extraction from Amino Acid Sequence 8.3 Relevance and Redundancy of Features 8.4 Multiobjective PSO-Based Feature Selection Technique 8.4.1 Particle Encoding 8.4.2 Initialization and Inputs 8.4.3 Objective Functions 8.4.4 Updating Position and Velocity 8.4.5 Updating Archive 8.4.6 Final Solution Selection 8.4.7 Overall MOPSO Algorithm 8.5 Other Comparative Methods 8.6 Dataset and Preprocessing 8.7 Experimental Results 8.7.1 Results 8.7.2 Results on Independent Dataset 8.8 Summary 9 Multiobjective Approach to Gene Ontology-Based Protein-Protein Interaction Prediction 9.1 Introduction 9.2 GO-Based Semantic Similarity 9.2.1 Resnik Measure 9.2.2 Lin Measure 9.2.3 Jiang-Conrath Measure 9.2.4 Relevance Measure 9.2.5 Cosine Measure 9.2.6 Kappa Measure 9.2.7 Czekanowski-Dice Measure 9.2.8 Weighted Jaccard Measure 9.2.9 Graph-Based Similarity Measure 9.2.10 Avg, Max, Rcmax 9.3 Dataset Preparation 9.3.1 Calculation of GO-Based Semantic Similarity of Protein Pairs 9.3.2 Dataset Creation 9.4 DEMO-Based Feature Selection 9.4.1 Chromosome Encoding 9.4.2 Evaluating Chromosomes 9.4.3 Offspring Creation 9.4.4 Truncation of Population 9.4.5 Selecting the Final Solution 9.5 Experimental Results 9.6 Summary 10 Multiobjective Approach to Protein Complex Detection 10.1 Introduction 10.2 Multiobjective Protein Complex Detection 10.2.1 Chromosome Representation 10.2.2 Population Initialization 10.2.3 Representation of Objective Functions 10.2.3.1 Topological Property-Based Objective Functions 10.2.3.2 Gene Ontology-Based Objective Function 10.2.4 Mutation Procedure 10.2.5 Final Solution 10.3 Experimental Results 10.3.1 Performance Comparisons Among Different Methods 10.3.1.1 Sensitivity 10.3.1.2 Positive Predictive Value 10.3.1.3 Accuracy 10.3.2 Analysis of Predicted Complexes 10.3.3 Association of Predicted Complexes in Disorders/Diseases 10.3.3.1 Involvement of Identified Complexes in 22 Primary Disorders/Disease Classes 10.3.3.2 Complex-Disease Bipartite Network 10.4 Summary 11 Multiobjective Biclustering for Analyzing HIV-1-Human Protein-Protein Interaction Network 11.1 Introduction 11.2 Strong PPI Module Finding Using Biclustering 11.2.1 Biclustering 11.2.2 Bipartite Graph Representation of PPIN 11.2.3 Quasi-Biclique Finding Through Biclustering 11.3 Multiobjective Biclustering for Finding Quasi-Bicliques 11.3.1 MOBICLUST Algorithm 11.4 Evaluation of MOBICLUST Using Artificial Data 11.4.1 Preparing the Artificial Dataset 11.4.2 Performance Metric 11.4.3 Results of Comparison 11.5 Analysis of Quasi-Bicliques from HIV-1-Human PPIN 11.5.1 Preparation of the HIV-1-Human PPIN 11.5.2 Results of MOBICLUST Biclustering 11.5.3 Biological Significance of the Quasi-Bicliques 11.5.4 Biological Significance of the Strong BipartiteModule 11.5.4.1 Study from Gene Ontology 11.5.4.2 Study from KEGG Pathway 11.5.4.3 Interactions Within Human PPIN 11.6 Summary References Index