This book represents the most comprehensive and up-to-date collection of information on the topic of computational molecular biology. Bringing the most recent research into the forefront of discussion, Algorithms in Computational Molecular Biology studies the most important and useful algorithms currently being used in the field, and provides related problems. It also succeeds where other titles have failed, in offering a wide range of information from the introductory fundamentals right up to the latest, most advanced levels of study.

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.

The most comprehensive, practical overview of algorithms in computational molecular biology

Computational molecular biology has emerged from the Human Genome Project as an important discipline for academic research and industrial application. Due to the exponential growth?in the size of biological databases and the increasing intricacy of biological problems, high-performance algorithms are now necessary to deal with errors in biological sequences.?Bringing the most recent research into the forefront of discussion, Algorithms in Computational Molecular Biology is the first in-depth examination of these important algorithms, which are based on the newest and most improved approaches and techniques in the field.

The book's unique coverage offers both a wide range of informationfrom theintroductory fundamentals right up to the latest, most advanced levels of studyand enough technical depth to be of practical use to working professionals. Organized into seven parts, it addresses:

• Strings processing and application to biological sequences
• Analysis of biological sequences
• Motif finding and structure prediction
• Phylogeny reconstruction
• Microarray data analysis
• Analysis of genomes
• Analysis of biological networks

Also featured are a combination of experiments and simulations that provide not only qualitative but also quantitative insights into this rich field. By covering a wide range of combinatorial problems that arise in computational molecular biology, this book enables researchers, computer scientists, life scientists, mathematicians, graduate students, and senior undergraduates to deal with more complex issues and richer data sets.

PREFACE xxxi

CONTRIBUTORS xxxiii

I STRINGS PROCESSING AND APPLICATION TO BIOLOGICAL SEQUENCES 1

1 STRING DATA STRUCTURES FOR COMPUTATIONAL MOLECULAR BIOLOGY 3
Christos Makris and Evangelos Theodoridis

2 EFFICIENT RESTRICTED-CASE ALGORITHMS FOR PROBLEMS IN COMPUTATIONAL BIOLOGY 27
Patricia A. Evans and H. Todd Wareham

3 FINITE AUTOMATA IN PATTERN MATCHING 51
Jan Holub

4 NEW DEVELOPMENTS IN PROCESSING OF DEGENERATE SEQUENCES 73
Pavlos Antoniou and Costas S. Iliopoulos

5 EXACT SEARCH ALGORITHMS FOR BIOLOGICAL SEQUENCES 91
Eric Rivals, Leena Salmela, and Jorma Tarhio

6 ALGORITHMIC ASPECTS OF ARC-ANNOTATED SEQUENCES 113
Guillaume Blin, Maxime Crochemore, and Stéphane Vialette

7 ALGORITHMIC ISSUES IN DNA BARCODING PROBLEMS 129
Bhaskar DasGupta, Ming-Yang Kao, and Ion Mandoiu

8 RECENT ADVANCES IN WEIGHTED DNA SEQUENCES 143
Manolis Christodoulakis and Costas S. Iliopoulos

9 DNA COMPUTING FOR SUBGRAPH ISOMORPHISM PROBLEM AND RELATED PROBLEMS 171
Sun-Yuan Hsieh, Chao-Wen Huang, and Hsin-Hung Chou

II ANALYSIS OF BIOLOGICAL SEQUENCES 191

10 GRAPHS IN BIOINFORMATICS 193
Elsa Chacko and Shoba Ranganathan

11 A FLEXIBLE DATA STORE FOR MANAGING BIOINFORMATICS DATA 221
Bassam A. Alqaralleh, Chen Wang, Bing Bing Zhou, and Albert Y. Zomaya

12 ALGORITHMS FOR THE ALIGNMENT OF BIOLOGICAL SEQUENCES 241
Ahmed Mokaddem and Mourad Elloumi

13 ALGORITHMS FOR LOCAL STRUCTURAL ALIGNMENT AND STRUCTURAL MOTIF IDENTIFICATION 261
Sanguthevar Rajasekaran, Vamsi Kundeti, and Martin Schiller

14 EVOLUTION OF THE CLUSTAL FAMILY OF MULTIPLE SEQUENCE ALIGNMENT PROGRAMS 277
Mohamed Radhouene Aniba and Julie Thompson

15 FILTERS AND SEEDS APPROACHES FOR FAST HOMOLOGY SEARCHES IN LARGE DATASETS 299
Nadia Pisanti, Mathieu Giraud, and Pierre Peterlongo

16 NOVEL COMBINATORIAL AND INFORMATION-THEORETIC ALIGNMENT-FREE DISTANCES FOR BIOLOGICAL DATA MINING 321
Chiara Epifanio, Alessandra Gabriele, Raffaele Giancarlo, and Marinella Sciortino

17 IN SILICO METHODS FOR THE ANALYSIS OF METABOLITES AND DRUG MOLECULES 361
Varun Khanna and Shoba Ranganathan

III MOTIF FINDING AND STRUCTURE PREDICTION 383

18 MOTIF FINDING ALGORITHMS IN BIOLOGICAL SEQUENCES 385
Tarek El Falah, Mourad Elloumi, and Thierry Lecroq

19 COMPUTATIONAL CHARACTERIZATION OF REGULATORY REGIONS 397
Enrique Blanco

20 ALGORITHMIC ISSUES IN THE ANALYSIS OF CHIP-SEQ DATA 425
Federico Zambelli and Giulio Pavesi

21 APPROACHES AND METHODS FOR OPERON PREDICTION BASED ON MACHINE LEARNING TECHNIQUES 449
Yan Wang, You Zhou, Chunguang Zhou, Shuqin Wang, Wei Du, Chen Zhang, and Yanchun Liang

22 PROTEIN FUNCTION PREDICTION WITH DATA-MINING TECHNIQUES 479
Xing-Ming Zhao and Luonan Chen

23 PROTEIN DOMAIN BOUNDARY PREDICTION 501
Paul D. Yoo, Bing Bing Zhou, and Albert Y. Zomaya

24 AN INTRODUCTION TO RNA STRUCTURE AND PSEUDOKNOT PREDICTION 521
Jana Sperschneider and Amitava Datta

IV PHYLOGENY RECONSTRUCTION 547

25 PHYLOGENETIC SEARCH ALGORITHMS FOR MAXIMUM LIKELIHOOD 549
Alexandros Stamatakis

26 HEURISTIC METHODS FOR PHYLOGENETIC RECONSTRUCTION WITH MAXIMUM PARSIMONY 579
Adrien Goëffon, Jean-Michel Richer, and Jin-Kao Hao

27 MAXIMUM ENTROPY METHOD FOR COMPOSITION VECTOR METHOD 599
Raymond H.-F. Chan, Roger W. Wang, and Jeff C.-F. Wong

V MICROARRAY DATA ANALYSIS 623

28 MICROARRAY GENE EXPRESSION DATA ANALYSIS 625
Alan Wee-Chung Liew and Xiangchao Gan

29 BICLUSTERING OF MICROARRAY DATA 651
Wassim Ayadi and Mourad Elloumi