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.3 Population Haplotyping / 12
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.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.5 Heuristic Algorithms for String Barcoding Problems / 39
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.3 Underlying Approach / 47
3.4 Experimental Results / 54
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.3 Motif Finding Algorithms / 70
4.4 Time Complexity / 75
4.5 Case Studies / 75
4.6 Conclusion / 80
References / 81
5 GLOBAL SEQUENCE ALIGNMENT WITH A BOUNDED NUMBER OF GAPS 83
Carl Barton, Tomás 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.3 Evaluation of Protein Secondary Structure Prediction Methods / 106
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.4 Postprocessing with A Generative Model / 119
7.5 Dedication to Protein Secondary Structure Prediction / 120
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.3 State of the Art / 135
8.4 A Novel Geometrical Approach to Motif Retrieval / 138
8.5 Implementation Notes / 149
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.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.3 Graph Mining / 172
10.4 Subgraph Mining / 173
10.5 Frequent Subgraph Discovery / 173
10.6 Feature Selection / 179
10.7 Feature Selection for Subgraphs / 180
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.3 Supervised Machine Learning Algorithm / 201
11.4 Fuzzy Application / 204
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.6 Domain Boundary Prediction Using Enhanced General Regression Network / 220
12.7 Inter-Domain Linkers Prediction Using Compositional Index and Simulated Annealing / 227
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.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.3 Template-Based Predictions / 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.3 Measuring Structural Similarity VIA MCES / 272
15.4 Protein Comparison VIA Graph Spectra / 279
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.5 Feature Selection / 299
16.6 Classification / 301
16.7 Evaluation and Analysis / 304
16.8 Results and Discussion / 304
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.3 Microarray Signal Analysis / 337
18.4 Algorithms for De Gene Selection / 339
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.4 RNA-Seq / 351
19.5 Benefits and Drawbacks of RNA-Seq and Microarray Technologies / 353
19.6 Gene Expression Profile Analysis / 356
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.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.2 Arrow Plot / 399
21.3 Significance Analysis of Microarrays / 404
21.4 Correspondence Analysis / 405
21.5 Impact of the Preprocessing Methods / 407
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, Agustín Sánchez-Cobos, and Miguel Arenas
23.1 Introduction / 440
23.2 Overview on Methods and Frameworks for Phylogenetic Tree Reconstruction / 440
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, Tomás Flouri, and Alexandros Stamatakis
24.1 Introduction / 457
24.2 Preliminaries / 459
24.3 A Naïve Approach / 462
24.4 Toward a Faster Method / 463
24.5 Improved Algorithm / 467
24.6 Implementation / 473
24.7 Evaluation / 474
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.3 Experimental Study / 491
25.4 Results and Discussion / 501
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.5 Learning Gene Regulation Networks / 532
27.6 Learning Species Interaction Networks / 540
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.3 Structural Equation Modeling / 560
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.4 Experimental Setup / 592
29.5 Experimental Analysis / 596
29.6 Conclusions / 605
Acknowledgments / 606
References / 606
INDEX 609
