The first comprehensive overview of preprocessing, mining, and postprocessing of biological data

Molecular biology is undergoing exponential growth in both the volume and complexity of biological data—and knowledge discovery offers the capacity to automate complex search and data analysis tasks. This book presents a vast overview of the most recent developments on techniques and approaches in the field of biological knowledge discovery and data mining (KDD)—providing in-depth fundamental and technical field information on the most important topics encountered.

Written by top experts, Biological Knowledge Discovery Handbook: Preprocessing, Mining, and Postprocessing of Biological Data covers the three main phases of knowledge discovery (data preprocessing, data processing—also known as data mining—and data postprocessing) and analyzes both verification systems and discovery systems.

BIOLOGICAL DATA PREPROCESSING

• Part A: Biological Data Management
• Part B: Biological Data Modeling
• Part C: Biological Feature Extraction
• Part D Biological Feature Selection

BIOLOGICAL DATA MINING

• Part E: Regression Analysis of Biological Data
• Part F Biological Data Clustering
• Part G: Biological Data Classification
• Part H: Association Rules Learning from Biological Data
• Part I: Text Mining and Application to Biological Data
• Part J: High-Performance Computing for Biological Data Mining

Combining sound theory with practical applications in molecular biology, Biological Knowledge Discovery Handbook is ideal for courses in bioinformatics and biological KDD as well as for practitioners and professional researchers in computer science, life science, and mathematics.

MOURAD ELLOUMI is a Full Professor in Computer Science at the University of Tunis-El Manar, Tunisia. He is the author/coauthor of more than fifty publications in international journals and conference proceedings and the coeditor, along with Albert Zomaya, of Algorithms in Computational Molecular Biology: Techniques, Approaches and Applications (Wiley).

ALBERT Y. ZOMAYA is the Chair Professor of High Performance Computing & Networking at The University of Sydney's School of Information Technologies. He is the author/coauthor of seven books, more than 450 publications in technical journals and conference proceedings, and the editor of fourteen books and nineteen conference volumes. He is a Fellow of the IEEE, the American Association for the Advancement of Science, and IET (UK).

PREFACE xiii

CONTRIBUTORS xv

SECTION I BIOLOGICAL DATA PREPROCESSING

PART A: BIOLOGICAL DATA MANAGEMENT

1 GENOME AND TRANSCRIPTOME SEQUENCE DATABASES FOR DISCOVERY, STORAGE, AND REPRESENTATION OF ALTERNATIVE SPLICING EVENTS 5
Bahar Taneri and Terry Gaasterland

2 CLEANING, INTEGRATING, AND WAREHOUSING GENOMIC DATA FROM BIOMEDICAL RESOURCES 35
Fouzia Moussouni and Laure Berti-Equille

3 CLEANSING OF MASS SPECTROMETRY DATA FOR PROTEIN IDENTIFICATION AND QUANTIFICATION 59
Penghao Wang and Albert Y. Zomaya

4 FILTERING PROTEIN–PROTEIN INTERACTIONS BY INTEGRATION OF ONTOLOGY DATA 77
Young-Rae Cho

PART B: BIOLOGICAL DATA MODELING

5 COMPLEXITY AND SYMMETRIES IN DNA SEQUENCES 95
Carlo Cattani

6 ONTOLOGY-DRIVEN FORMAL CONCEPTUAL DATA MODELING FOR BIOLOGICAL DATA ANALYSIS 129
Catharina Maria Keet

7 BIOLOGICAL DATA INTEGRATION USING NETWORK MODELS 155
Gaurav Kumar and Shoba Ranganathan

8 NETWORK MODELING OF STATISTICAL EPISTASIS 175
Ting Hu and Jason H. Moore

9 GRAPHICAL MODELS FOR PROTEIN FUNCTION AND STRUCTURE PREDICTION 191
Mingjie Tang, Kean Ming Tan, Xin Lu Tan, Lee Sael, Meghana Chitale, Juan Esquivel-Rodr?guez, and Daisuke Kihara

PART C: BIOLOGICAL FEATURE EXTRACTION

10 ALGORITHMS AND DATA STRUCTURES FOR NEXT-GENERATION SEQUENCES 225
Francesco Vezzi, Giuseppe Lancia, and Alberto Policriti

11 ALGORITHMS FOR NEXT-GENERATION SEQUENCING DATA 251
Costas S. Iliopoulos and Solon P. Pissis

12 GENE REGULATORY NETWORK IDENTIFICATION WITH QUALITATIVE PROBABILISTIC NETWORKS 281
Zina M. Ibrahim, Alioune Ngom, and Ahmed Y. Tawfik

PART D: BIOLOGICAL FEATURE SELECTION

13 COMPARING, RANKING, AND FILTERING MOTIFS WITH
CHARACTER CLASSES: APPLICATION TO BIOLOGICAL SEQUENCES ANALYSIS 309
Matteo Comin and Davide Verzotto

14 STABILITY OF FEATURE SELECTION ALGORITHMS AND ENSEMBLE FEATURE SELECTION METHODS IN
BIOINFORMATICS 333
Pengyi Yang, Bing B. Zhou, Jean Yee-Hwa Yang, and Albert Y. Zomaya

15 STATISTICAL SIGNIFICANCE ASSESSMENT FOR BIOLOGICAL FEATURE SELECTION: METHODS AND ISSUES 353
Juntao Li, Kwok Pui Choi, Yudi Pawitan, and Radha Krishna Murthy Karuturi

16 SURVEY OF NOVEL FEATURE SELECTION METHODS FOR CANCER CLASSIFICATION 379
Oleg Okun

17 INFORMATION-THEORETIC GENE SELECTION IN EXPRESSION DATA 399
Patrick E. Meyer and Gianluca Bontempi

18 FEATURE SELECTION AND CLASSIFICATION FOR GENE EXPRESSION DATA USING EVOLUTIONARY COMPUTATION 421
Haider Banka, Suresh Dara, and Mourad Elloumi

SECTION II BIOLOGICAL DATA MINING

PART E: REGRESSION ANALYSIS OF BIOLOGICAL DATA

19 BUILDING VALID REGRESSION MODELS FOR BIOLOGICAL DATA USING STATA AND R 445
Charles Lindsey and Simon J. Sheather

20 LOGISTIC REGRESSION IN GENOMEWIDE ASSOCIATION ANALYSIS 477
Wentian Li and Yaning Yang

21 SEMIPARAMETRIC REGRESSION METHODS IN LONGITUDINAL DATA: APPLICATIONS TO AIDS CLINICAL TRIAL DATA 501
Yehua Li

PART F: BIOLOGICAL DATA CLUSTERING

22 THE THREE STEPS OF CLUSTERING IN THE POST-GENOMIC ERA 521
Raffaele Giancarlo, Giosu´e Lo Bosco, Luca Pinello, and Filippo Utro

23 CLUSTERING ALGORITHMS OF MICROARRAY DATA 557
Haifa Ben Saber, Mourad Elloumi, and Mohamed Nadif

24 SPREAD OF EVALUATION MEASURES FOR MICROARRAY CLUSTERING 569
Giulia Bruno and Alessandro Fiori

25 SURVEY ON BICLUSTERING OF GENE EXPRESSION DATA 591
Adelaide Valente Freitas, Wassim Ayadi, Mourad Elloumi, Jose Luis Oliveira, and Jin-Kao Hao

26 MULTIOBJECTIVE BICLUSTERING OF GENE EXPRESSION DATA WITH BIOINSPIRED ALGORITHMS 609
Khedidja Seridi, Laetitia Jourdan, and El-Ghazali Talbi

27 COCLUSTERING UNDER GENE ONTOLOGY DERIVED CONSTRAINTS FOR PATHWAY IDENTIFICATION 625
Alessia Visconti, Francesca Cordero, Dino Ienco, and Ruggero G. Pensa

PART G: BIOLOGICAL DATA CLASSIFICATION

28 SURVEY ON FINGERPRINT CLASSIFICATION METHODS FOR BIOLOGICAL SEQUENCES 645
Bhaskar DasGupta and Lakshmi Kaligounder

29 MICROARRAY DATA ANALYSIS: FROM PREPARATION TO CLASSIFICATION 657
Luciano Cascione, Alfredo Ferro, Rosalba Giugno, Giuseppe Pigola, and Alfredo Pulvirenti

30 DIVERSIFIED CLASSIFIER FUSION TECHNIQUE FOR GENE EXPRESSION DATA 675
Sashikala Mishra, Kailash Shaw, and Debahuti Mishra

31 RNA CLASSIFICATION AND STRUCTURE PREDICTION: ALGORITHMS AND CASE STUDIES 685
Ling Zhong, Junilda Spirollari, Jason T. L. Wang, and Dongrong Wen

32 AB INITIO PROTEIN STRUCTURE PREDICTION: METHODS AND CHALLENGES 703
Jad Abbass, Jean-Christophe Nebel, and Nashat Mansour

33 OVERVIEW OF CLASSIFICATION METHODS TO
SUPPORT HIV/AIDS CLINICAL DECISION MAKING 725
Khairul A. Kasmiran, Ali Al Mazari, Albert Y. Zomaya, and Roger J. Garsia

PART H: ASSOCIATION RULES LEARNING FROM BIOLOGICAL DATA

34 MINING FREQUENT PATTERNS AND ASSOCIATION RULES FROM BIOLOGICAL DATA 737
Ioannis Kavakiotis, George Tzanis, and Ioannis Vlahavas

35 GALOIS CLOSURE BASED ASSOCIATION RULE MINING FROM BIOLOGICAL DATA 761
Kartick Chandra Mondal and Nicolas Pasquier

36 INFERENCE OF GENE REGULATORY NETWORKS BASED ON ASSOCIATION RULES 803
Cristian Andres Gallo, Jessica Andrea Carballido, and Ignacio Ponzoni

PART I: TEXT MINING AND APPLICATION TO BIOLOGICAL DATA

37 CURRENT METHODOLOGIES FOR BIOMEDICAL NAMED ENTITY RECOGNITION 841
David Campos, Sergio Matos, and José Lu?s Oliveira

38 AUTOMATED ANNOTATION OF SCIENTIFIC DOCUMENTS: INCREASING ACCESS TO BIOLOGICAL KNOWLEDGE 869
Evangelos Pafilis, Heiko Horn, and Nigel P. Brown

39 AUGMENTING BIOLOGICAL TEXT MINING WITH SYMBOLIC INFERENCE 901
Jong C. Park and Hee-Jin Lee

40 WEB CONTENT MINING FOR LEARNING GENERIC RELATIONS AND THEIR ASSOCIATIONS FROM TEXTUAL BIOLOGICAL DATA 919
Muhammad Abulaish and Jahiruddin

41 PROTEIN–PROTEIN RELATION EXTRACTION FROM BIOMEDICAL ABSTRACTS 943
Syed Toufeeq Ahmed, Hasan Davulcu, Sukru Tikves, Radhika Nair, and Chintan Patel

PART J: HIGH-PERFORMANCE COMPUTING FOR BIOLOGICAL DATA MINING

42 ACCELERATING PAIRWISE ALIGNMENT ALGORITHMS BY USING GRAPHICS PROCESSOR UNITS 971
Mourad Elloumi, Mohamed Al Sayed Issa, and Ahmed Mokaddem

43 HIGH-PERFORMANCE COMPUTING IN HIGH-THROUGHPUT SEQUENCING 981
Kamer Kaya, Ayat Hatem, Hatice Gulcin Ozer, Kun Huang, and Umit V. Catalyurek

44 LARGE-SCALE CLUSTERING OF SHORT READS FOR METAGENOMICS ON GPUs 1003
Thuy Diem Nguyen, Bertil Schmidt, Zejun Zheng, and Chee Keong Kwoh

SECTION III BIOLOGICAL DATA POSTPROCESSING

PART K: BIOLOGICAL KNOWLEDGE INTEGRATION AND VISUALIZATION

45 INTEGRATION OF METABOLIC KNOWLEDGE FOR GENOME-SCALE METABOLIC RECONSTRUCTION 1027
Ali Masoudi-Nejad, Ali Salehzadeh-Yazdi, Shiva Akbari-Birgani, and Yazdan Asgari

46 INFERRING AND POSTPROCESSING HUGE PHYLOGENIES 1049
Stephen A. Smith and Alexandros Stamatakis

47 BIOLOGICAL KNOWLEDGE VISUALIZATION 1073
Rodrigo Santamar?a

48 VISUALIZATION OF BIOLOGICAL KNOWLEDGE BASED ON MULTIMODAL BIOLOGICAL DATA 1109
Hendrik Rohn and Falk Schreiber

INDEX 1127