Algorithms in Computational Molecular Biology

Mourad Elloumi, PhD, is Associate Professor in Computer Science, Faculty of Economic Sciences and Management of Tunis (Tunisia), and member of the Unit of Technologies of Information and Communication (UTIC). He is the author/coauthor of more than forty publications in international journals and conferences. Professor Elloumi was the guest editor of a special issue on biological knowledge discovery and data mining in Knowledge-Based Systems and the coeditor of the proceedings of two international conferences.Albert Y. Zomaya, PhD, is the Chair Professor of High Performance Computing and Networking in the School of Information Technologies at The University of Sydney (Australia). He is the author/coauthor of eight books and more than 400 publications in technical journals and conferences, and the editor of eight books and eight conference volumes. Professor Zomaya is currently an associate editor for twenty journals, the Founding Editor of the Wiley Series on Parallel and Distributed Computing, and a Founding Coeditor of the Wiley Series in Bioinformatics.

• PREFACE xxxiCONTRIBUTORS xxxiiiI STRINGS PROCESSING AND APPLICATION TO BIOLOGICAL SEQUENCES 11 STRING DATA STRUCTURES FOR COMPUTATIONAL MOLECULAR BIOLOGY 3Christos Makris and Evangelos Theodoridis2 EFFICIENT RESTRICTED-CASE ALGORITHMS FOR PROBLEMS IN COMPUTATIONAL BIOLOGY 27Patricia A. Evans and H. Todd Wareham3 FINITE AUTOMATA IN PATTERN MATCHING 51Jan Holub4 NEW DEVELOPMENTS IN PROCESSING OF DEGENERATE SEQUENCES 73Pavlos Antoniou and Costas S. Iliopoulos5 EXACT SEARCH ALGORITHMS FOR BIOLOGICAL SEQUENCES 91Eric Rivals, Leena Salmela, and Jorma Tarhio6 ALGORITHMIC ASPECTS OF ARC-ANNOTATED SEQUENCES 113Guillaume Blin, Maxime Crochemore, and Stéphane Vialette7 ALGORITHMIC ISSUES IN DNA BARCODING PROBLEMS 129Bhaskar DasGupta, Ming-Yang Kao, and Ion Mandoiu8 RECENT ADVANCES IN WEIGHTED DNA SEQUENCES 143Manolis Christodoulakis and Costas S. Iliopoulos9 DNA COMPUTING FOR SUBGRAPH ISOMORPHISM PROBLEM AND RELATED PROBLEMS 171Sun-Yuan Hsieh, Chao-Wen Huang, and Hsin-Hung ChouII ANALYSIS OF BIOLOGICAL SEQUENCES 19110 GRAPHS IN BIOINFORMATICS 193Elsa Chacko and Shoba Ranganathan11 A FLEXIBLE DATA STORE FOR MANAGING BIOINFORMATICS DATA 221Bassam A. Alqaralleh, Chen Wang, Bing Bing Zhou, and Albert Y. Zomaya12 ALGORITHMS FOR THE ALIGNMENT OF BIOLOGICAL SEQUENCES 241Ahmed Mokaddem and Mourad Elloumi13 ALGORITHMS FOR LOCAL STRUCTURAL ALIGNMENT AND STRUCTURAL MOTIF IDENTIFICATION 261Sanguthevar Rajasekaran, Vamsi Kundeti, and Martin Schiller14 EVOLUTION OF THE CLUSTAL FAMILY OF MULTIPLE SEQUENCE ALIGNMENT PROGRAMS 277Mohamed Radhouene Aniba and Julie Thompson15 FILTERS AND SEEDS APPROACHES FOR FAST HOMOLOGY SEARCHES IN LARGE DATASETS 299Nadia Pisanti, Mathieu Giraud, and Pierre Peterlongo16 NOVEL COMBINATORIAL AND INFORMATION-THEORETIC ALIGNMENT-FREE DISTANCES FOR BIOLOGICAL DATA MINING 321Chiara Epifanio, Alessandra Gabriele, Raffaele Giancarlo, and Marinella Sciortino17 IN SILICO METHODS FOR THE ANALYSIS OF METABOLITES AND DRUG MOLECULES 361Varun Khanna and Shoba RanganathanIII MOTIF FINDING AND STRUCTURE PREDICTION 38318 MOTIF FINDING ALGORITHMS IN BIOLOGICAL SEQUENCES 385Tarek El Falah, Mourad Elloumi, and Thierry Lecroq19 COMPUTATIONAL CHARACTERIZATION OF REGULATORY REGIONS 397Enrique Blanco20 ALGORITHMIC ISSUES IN THE ANALYSIS OF CHIP-SEQ DATA 425Federico Zambelli and Giulio Pavesi21 APPROACHES AND METHODS FOR OPERON PREDICTION BASED ON MACHINE LEARNING TECHNIQUES 449Yan Wang, You Zhou, Chunguang Zhou, Shuqin Wang, Wei Du, Chen Zhang, and Yanchun Liang22 PROTEIN FUNCTION PREDICTION WITH DATA-MINING TECHNIQUES 479Xing-Ming Zhao and Luonan Chen23 PROTEIN DOMAIN BOUNDARY PREDICTION 501Paul D. Yoo, Bing Bing Zhou, and Albert Y. Zomaya24 AN INTRODUCTION TO RNA STRUCTURE AND PSEUDOKNOT PREDICTION 521Jana Sperschneider and Amitava DattaIV PHYLOGENY RECONSTRUCTION 54725 PHYLOGENETIC SEARCH ALGORITHMS FOR MAXIMUM LIKELIHOOD 549Alexandros Stamatakis26 HEURISTIC METHODS FOR PHYLOGENETIC RECONSTRUCTION WITH MAXIMUM PARSIMONY 579Adrien Goëffon, Jean-Michel Richer, and Jin-Kao Hao27 MAXIMUM ENTROPY METHOD FOR COMPOSITION VECTOR METHOD 599Raymond H.-F. Chan, Roger W. Wang, and Jeff C.-F. WongV MICROARRAY DATA ANALYSIS 62328 MICROARRAY GENE EXPRESSION DATA ANALYSIS 625Alan Wee-Chung Liew and Xiangchao Gan29 BICLUSTERING OF MICROARRAY DATA 651Wassim Ayadi and Mourad Elloumi30 COMPUTATIONAL MODELS FOR CONDITION-SPECIFIC GENE AND PATHWAY INFERENCE 665Yu-Qing Qiu, Shihua Zhang, Xiang-Sun Zhang, and Luonan Chen31 HETEROGENEITY OF DIFFERENTIAL EXPRESSION IN CANCER STUDIES: ALGORITHMS AND METHODS 691Radha Krishna Murthy KaruturiVI ANALYSIS OF GENOMES 72332 COMPARATIVE GENOMICS: ALGORITHMS AND APPLICATIONS 725Xiao Yang and Srinivas Aluru33 ADVANCES IN GENOME REARRANGEMENT ALGORITHMS 749Masud Hasan and M. Sohel Rahman34 COMPUTING GENOMIC DISTANCES: AN ALGORITHMIC VIEWPOINT 773Guillaume Fertin and Irena Rusu35 WAVELET ALGORITHMS FOR DNA ANALYSIS 799Carlo Cattani36 HAPLOTYPE INFERENCE MODELS AND ALGORITHMS 843Ling-Yun WuVII ANALYSIS OF BIOLOGICAL NETWORKS 86537 UNTANGLING BIOLOGICAL NETWORKS USING BIOINFORMATICS 867Gaurav Kumar, Adrian P. Cootes, and Shoba Ranganathan38 PROBABILISTIC APPROACHES FOR INVESTIGATING BIOLOGICAL NETWORKS 893Jérémie Bourdon and Damien Eveillard39 MODELING AND ANALYSIS OF BIOLOGICAL NETWORKS WITH MODEL CHECKING 915Dragan Bosnacki, Peter A.J. Hilbers, Ronny S. Mans, and Erik P. de Vink40 REVERSE ENGINEERING OF MOLECULAR NETWORKS FROM A COMMON COMBINATORIAL APPROACH 941Bhaskar DasGupta, Paola Vera-Licona, and Eduardo Sontag41 UNSUPERVISED LEARNING FOR GENE REGULATION NETWORK INFERENCE FROM EXPRESSION DATA: A REVIEW 955Mohamed Elati and Céline Rouveirol42 APPROACHES TO CONSTRUCTION AND ANALYSIS OF MICRORNA-MEDIATED NETWORKS 979Ilana Lichtenstein, Albert Zomaya, Jennifer Gamble, and Mathew VadasINDEX 1007