Algorithms in Computational Molecular Biology: Techniques, Approaches and Applications

ALGORITHMS IN
COMPUTATIONAL
MOLECULAR BIOLOGY......Page 5
CONTENTS......Page 9
PREFACE......Page 33
CONTRIBUTORS......Page 35
I STRINGS PROCESSING AND APPLICATION TO BIOLOGICAL SEQUENCES......Page 41
1.1 Introduction......Page 43
1.2.1 Suffix Trees......Page 46
1.2.2 Suffix Arrays......Page 48
1.3 Index Structures for Weighted Strings......Page 52
1.4 Index Structures for Indeterminate Strings......Page 54
1.5 String Data Structures in Memory Hierarchies......Page 57
References......Page 60
2.1 The Need for Special Cases......Page 67
2.2 Assessing Efficient Solvability Options for General Problems and Special Cases......Page 68
2.3 String and Sequence Problems......Page 70
2.4 Shortest Common Superstring......Page 71
2.4.1 Solving the General Problem......Page 72
2.4.2 Special Case: SCSt for Short Strings Over Small Alphabets......Page 74
2.4.3 Discussion......Page 75
2.5 Longest Common Subsequence......Page 76
2.5.1 Solving the General Problem......Page 77
2.5.3 Special Case: LCS Under Symbol-Occurrence Restrictions......Page 79
2.5.4 Discussion......Page 80
2.6 Common Approximate Substring......Page 81
2.6.1 Solving the General Problem......Page 82
2.6.2 Special Case: Common Approximate String......Page 84
2.6.3 Discussion......Page 85
2.7 Conclusion......Page 86
References......Page 87
3.1 Introduction......Page 91
3.1.1 Preliminaries......Page 92
3.2.1 Forward Automata......Page 93
3.2.2 Degenerate Strings......Page 96
3.2.3 Indexing Automata......Page 97
3.2.5 Backward Automata......Page 99
3.3 NFA Simulation......Page 100
3.3.2 Bit Parallelism......Page 101
3.3.3 Dynamic Programming......Page 103
3.4 Finite Automaton as Model of Computation......Page 106
3.6 Summary......Page 107
References......Page 109
4.1 Introduction......Page 113
4.2 Background......Page 114
4.3 Basic Definitions......Page 116
4.4.2 Computing the Smallest Cover of the Degenerate String x......Page 119
4.4.3 Computing Maximal Local Covers of x......Page 121
4.5 Conservative String Covering in Degenerate Strings......Page 124
4.5.1 Finding Constrained Pattern p in Degenerate String T......Page 125
4.5.2 Computing λ-Conservative Covers of Degenerate Strings......Page 126
4.5.3 Computing λ-Conservative Seeds of Degenerate Strings......Page 127
4.6 Conclusion......Page 128
References......Page 129
5.1 Introduction......Page 131
5.2 Single Pattern Matching Algorithms......Page 133
5.2.1 Algorithms for DNA Sequences......Page 134
5.2.2 Algorithms for Amino Acids......Page 136
5.3.1 Trie-Based Algorithms......Page 137
5.3.2 Filtering Algorithms......Page 140
5.4.1 MPSCAN: An Efficient Exact Set Pattern Matching Tool for DNA/RNA Sequences......Page 143
5.4.2 Other Solutions for Mapping Reads......Page 144
5.4.3 Comparison of Mapping Solutions......Page 145
5.5 Conclusions......Page 147
References......Page 148
6.1 Introduction......Page 153
6.2.2 Hierarchy......Page 154
6.2.4 Alignment......Page 155
6.2.5 Edit Operations......Page 156
6.3.1 Definition......Page 157
6.3.2 Classical Complexity......Page 158
6.3.3 Parameterized Complexity......Page 159
6.4.1 Definition......Page 160
6.4.3 Classical Complexity for the Refined Hierarchy......Page 161
6.5.1 Definition......Page 162
6.6.2 Classical Complexity......Page 163
References......Page 165
7.1 Introduction......Page 169
7.2 Test Set Problems: A General Framework for Several Barcoding Problems......Page 170
7.3 A Synopsis of Biological Applications of Barcoding......Page 172
7.4 Survey of Algorithmic Techniques on Barcoding......Page 173
7.4.3 Provably Asymptotically Optimal Results......Page 174
7.5 Information Content Approach......Page 175
7.6 Set-Covering Approach......Page 176
7.6.1 Set-Covering Implementation in More Detail......Page 177
7.7.1 Randomly Generated Instances......Page 179
7.8 Concluding Remarks......Page 180
References......Page 181
8.1 Introduction......Page 183
8.2.1 Strings......Page 186
8.2.2 Weighted Sequences......Page 187
8.3.1 Weighted Suffix Tree......Page 188
8.3.2 Property Suffix Tree......Page 191
8.4.1 Pattern Matching Using the Weighted Suffix Tree......Page 192
8.4.2 Pattern Matching Using Match Counts......Page 193
8.4.3 Pattern Matching with Gaps......Page 194
8.4.4 Pattern Matching with Swaps......Page 196
8.5.1 Hamming Distance......Page 197
8.6 Repetitions, Covers, and Tandem Repeats......Page 200
8.6.2 Fixed-Length Simple Repetitions......Page 201
8.6.4 Fixed-Length Tandem Repeats......Page 203
8.7.1 Approximate Motifs in a Single Weighted Sequence......Page 204
8.7.2 Approximate Common Motifs in a Set of Weighted Sequences......Page 205
8.8 Conclusions......Page 206
References......Page 207
9.1 Introduction......Page 211
9.2 Definitions of Subgraph Isomorphism Problem and Related Problems......Page 212
9.3.1 The Stickers......Page 214
9.4 The Sticker-based Solution Space......Page 215
9.4.1 Using Stickers for Generating the Permutation Set......Page 216
9.4.2 Using Stickers for Generating the Solution Space......Page 217
9.5.1 Solving the Subgraph Isomorphism Problem......Page 219
9.5.2 Solving the Graph Isomorphism Problem......Page 223
9.5.3 Solving the Maximum Common Subgraph Problem......Page 224
9.6 Experimental Data......Page 227
References......Page 228
II ANALYSIS OF BIOLOGICAL SEQUENCES......Page 231
10.1.1 What is a Graph?......Page 233
10.1.2 Types of Graphs......Page 234
10.1.3 Well-Known Graph Problems and Algorithms......Page 240
10.2.1 Alternative Splicing and Graphs......Page 247
10.2.2 Evolutionary Tree Construction......Page 248
10.2.3 Tracking the Temporal Variation of Biological
Systems......Page 249
10.2.4 Identifying Protein Domains by Clustering Sequence Alignments......Page 250
10.2.5 Clustering Gene Expression Data......Page 251
10.2.7 Optimal Design of Thermally Stable Proteins......Page 252
10.2.8 The Sequencing by Hybridization (SBH) Problem......Page 254
10.2.9 Predicting Interactions in Protein Networks by Completing Defective Cliques......Page 255
References......Page 256
11.1 Introduction......Page 261
11.1.2 Scalability Challenges......Page 262
11.2 Data Model and System Overview......Page 263
11.3 Replication and Load Balancing......Page 267
11.3.1 Replicating an Index Node......Page 268
11.3.2 Answering Range Queries with Replicas......Page 269
11.4.1 Point Query Processing Performance......Page 270
11.4.2 Range Query Processing Performance......Page 273
11.4.3 Growth of the Replicas of an Indexing Node......Page 275
11.6 Summary......Page 277
References......Page 278
12.1 Introduction......Page 281
12.2.1 Pairwise Alignment Algorithms......Page 282
12.2.2 Multiple Alignment Algorithms......Page 285
12.3 Score Functions......Page 290
12.4 Benchmarks......Page 292
References......Page 295
13.1 Introduction......Page 301
13.2 Problem Definition of Local Structural Alignment......Page 302
13.3.1 Alignment Fragment Pairs......Page 303
13.3.2 Finding the Optimal Local Alignments Based on the VLAFP Cost Function......Page 304
13.4.1 Description of Protein Structure in PDB Format......Page 306
13.4.3 Center-of-Gravity-Based Algorithm......Page 307
13.4.4 Extending Theorem 13.1 for Atomic Coordinates in Protein Structure......Page 309
13.5 Searching Structural Motifs......Page 310
13.8 Accuracy Results......Page 313
13.9 Conclusion......Page 314
Acknowledgments......Page 315
References......Page 316
14.1 Introduction......Page 317
14.2 Clustal-ClustalV......Page 318
14.2.1 Pairwise Similarity Scores......Page 319
14.2.2 Guide Tree......Page 320
14.2.4 An Efficient Dynamic Programming Algorithm......Page 321
14.3.2 More Accurate Guide Tree......Page 324
14.3.3 Improved Progressive Alignment......Page 325
14.4 ClustalX......Page 329
14.4.1 Alignment Quality Analysis......Page 330
14.5 ClustalW and ClustalX 2.0......Page 332
14.6 DbClustal......Page 333
14.6.1 Anchored Global Alignment......Page 334
14.7 Perspectives......Page 335
References......Page 336
15.1.1 Homologies and Large Datasets......Page 339
15.1.3 Contents......Page 340
15.2.2 Filters—Fundamental Concepts......Page 341
15.3.1 History of Lossless Filters......Page 343
15.3.2 Quasar and swift—Filtering Repeats with Edit Distance......Page 344
15.3.3 Nimbus—Filtering Multiple Repeats with Hamming Distance......Page 345
15.3.4 tuiuiu—Filtering Multiple Repeats with Edit Distance......Page 348
15.4 Lossy Seed-Based Filters......Page 349
15.4.1 Seed-Based Heuristics......Page 350
15.4.3 Latencies and Neighborhood Indexing......Page 351
15.4.4 Seed-Based Heuristics Implementations......Page 353
References......Page 355
16.1 Introduction......Page 361
16.2 Information-Theoretic Alignment-Free Methods......Page 363
16.2.1 Fundamental Information Measures, Statistical Dependency, and Similarity of Sequences......Page 364
16.2.2 Methods Based on Relative Entropy and Empirical Probability Distributions......Page 365
16.2.3 A Method Based on Statistical Dependency, via Mutual Information......Page 369
16.3 Combinatorial Alignment-Free Methods......Page 371
16.3.1 The Average Common Substring Distance......Page 372
16.3.2 A Method Based on the EBWT Transform......Page 373
16.3.3 N-Local Decoding......Page 374
16.4 Alignment-Free Compositional Methods......Page 376
16.4.1 The k-String Composition Approach......Page 377
16.4.2 Complete Composition Vector......Page 378
16.4.3 Fast Algorithms to Compute Composition Vectors......Page 379
16.5.1 D2 and its Distributional Regimes......Page 380
16.5.2 An Extension to Mismatches and the Choice of the Optimal Word Size......Page 382
16.5.3 The Transformation of D2 into a Method Assessing the Statistical Significance of Sequence Similarity......Page 383
16.6 Domains of Biological Application......Page 384
16.6.1 Phylogeny: Information Theoretic and Combinatorial Methods......Page 385
16.6.2 Phylogeny: Compositional Methods......Page 386
16.6.3 CIS Regulatory Modules......Page 387
16.6.4 DNA Sequence Dependencies......Page 388
16.7 Datasets and Software for Experimental Algorithmics......Page 389
16.7.1 Datasets......Page 390
16.7.2 Software......Page 393
16.8 Conclusions......Page 394
References......Page 395
17.1.1 Chemoinformatics and “Drug-Likeness”......Page 401
17.2.1 One-Dimensional (1-D) Descriptors......Page 403
17.2.2 Two-Dimensional (2-D) Descriptors......Page 404
17.2.3 Three-Dimensional (3-D) Descriptors......Page 406
17.3.1 PubChem......Page 407
17.3.5 ChemDB......Page 409
17.4.1 Simple Count Methods......Page 410
17.4.2 Enhanced Simple Count Methods, Using Structural Features......Page 411
17.4.3 ML Methods......Page 412
17.5 Conclusions......Page 416
References......Page 417
III MOTIF FINDING AND STRUCTURE PREDICTION......Page 423
18.1 Introduction......Page 425
18.2 Preliminaries......Page 426
18.3.2 Algorithms......Page 427
18.4.2 Algorithms......Page 431
18.5.1 Formulation......Page 432
18.6.1 Formulation......Page 433
18.6.2 Algorithms......Page 434
18.7 Conclusion......Page 435
References......Page 436
19.1 The Genome Regulatory Landscape......Page 437
19.2 Qualitative Models of Regulatory Signals......Page 440
19.3 Quantitative Models of Regulatory Signals......Page 441
19.4 Detection of Dependencies in Sequences......Page 443
19.5 Repositories of Regulatory Information......Page 445
19.6 Using Predictive Models to Annotate Sequences......Page 446
19.7 Comparative Genomics Characterization......Page 448
19.8 Sequence Comparisons......Page 450
19.9 Combining Motifs and Alignments......Page 452
19.10 Experimental Validation......Page 454
References......Page 457
20.1 Introduction......Page 465
20.2 Mapping Sequences on the Genome......Page 469
20.3 Identifying Significantly Enriched Regions......Page 474
20.3.1 ChIP-Seq Approaches to the Identification of DNA Structure Modifications......Page 477
20.4 Deriving Actual Transcription Factor Binding Sites......Page 478
References......Page 484
21.1 Introduction......Page 489
21.2.1 Operon Datasets......Page 491
21.2.2 Features......Page 494
21.2.3 Preprocess Methods......Page 499
21.3 Machine Learning Prediction Methods for Operon Prediction......Page 500
21.3.1 Hidden Markov Model......Page 501
21.3.2 Linkage Clustering......Page 502
21.3.3 Bayesian Classifier......Page 504
21.3.4 Bayesian Network......Page 507
21.3.5 Support Vector Machine......Page 508
21.3.6 Artificial Neural Network......Page 510
21.3.7 Genetic Algorithms......Page 511
21.3.8 Several Combinations......Page 512
21.4 Conclusions......Page 514
References......Page 515
22.1 Introduction......Page 519
22.2.1 Protein Sequence Classification......Page 520
22.2.2 Protein Subcellular Localization Prediction......Page 523
22.3 Protein Annotation Based on Protein Structure......Page 524
22.4 Protein Function Prediction Based on Gene-Expression Data......Page 525
22.5.1 Protein Function Prediction Based on Local Topology Structure of Interaction Map......Page 526
22.5.2 Protein Function Prediction Based on Global Topology of Interaction Map......Page 528
22.6 Protein Function Prediction Based on Data Integration......Page 529
22.7 Conclusions and Perspectives......Page 531
References......Page 533
23.1 Introduction......Page 541
23.2 Profiling Technique......Page 543
23.2.2 Hierarchical Mixture of Experts......Page 546
23.2.3 Overall Modular Kernel Architecture......Page 548
23.3 Results......Page 550
23.4.1 Nonlocal Interactions in Amino Acids......Page 552
23.4.2 Secondary Structure Information......Page 553
23.4.4 Domain Assignment Is More Accurate for Proteins with Fewer Domains......Page 554
References......Page 555
24.1 Introduction......Page 561
24.2 RNA Secondary Structure Prediction......Page 562
24.2.1 Minimum Free Energy Model......Page 564
24.2.2 Prediction of Minimum Free Energy Structure......Page 566
24.2.3 Partition Function Calculation......Page 570
24.2.4 Base Pair Probabilities......Page 573
24.3 RNA Pseudoknots......Page 574
24.3.1 Biological Relevance......Page 576
24.3.2 RNA Pseudoknot Prediction......Page 577
24.3.3 Dynamic Programming......Page 578
24.3.4 Heuristic Approaches......Page 581
24.3.6 Overview......Page 582
24.4 Conclusions......Page 583
References......Page 584
IV PHYLOGENY RECONSTRUCTION......Page 587
25.1 Introduction......Page 589
25.1.1 Phylogenetic Inference......Page 590
25.2 Computing the Likelihood......Page 592
25.3.1 Reuse of Values Across Probability Vectors......Page 595
25.3.2 Gappy Alignments and Pointer Meshes......Page 597
25.4 Alignment Shapes......Page 598
25.5 General Search Heuristics......Page 599
25.5.1 Lazy Evaluation Strategies......Page 603
25.5.2 Further Heuristics......Page 604
25.5.3 Rapid Bootstrapping......Page 605
25.6 Computing the Robinson Foulds Distance......Page 606
25.7 Convergence Criteria......Page 608
25.7.1 Asymptotic Stopping......Page 609
25.8 Future Directions......Page 612
References......Page 613
26.1 Introduction......Page 619
26.2.1 Parsimony and Maximum Parsimony......Page 620
26.3.1 Combinatorial Optimization......Page 621
26.3.3 Local Search Methods......Page 622
26.3.4 Evolutionary Metaheuristics and Genetic Algorithms......Page 628
26.3.5 Memetic Methods......Page 630
26.3.6 Problem-Specific Improvements......Page 632
26.4 Conclusion......Page 634
References......Page 635
27.1 Introduction......Page 639
27.2.1 Definitions......Page 641
27.2.2 Denoising Formulas......Page 643
27.2.3 Distance Measure......Page 651
27.2.4 Phylogenetic Tree Construction......Page 653
27.3.2 Example 2......Page 654
27.3.3 Example 3......Page 655
27.3.4 Example 4......Page 657
References......Page 659
V MICROARRAY DATA ANALYSIS......Page 663
28.1 Introduction......Page 665
28.2 DNA Microarray Technology and Experiment......Page 666
28.3 Image Analysis and Expression Data Extraction......Page 667
28.3.4 Spot Extraction......Page 668
28.4.2 Normalization......Page 670
28.5 Missing Value Imputation......Page 671
28.6 Temporal Gene Expression Profile Analysis......Page 674
28.7 Cyclic Gene Expression Profiles Detection......Page 680
28.7.1 SSA-AR Spectral Estimation......Page 683
28.7.2 Spectral Estimation by Signal Reconstruction......Page 684
28.7.3 Statistical Hypothesis Testing for Periodic Profile Detection......Page 686
28.8 Summary......Page 687
Acknowledgments......Page 688
References......Page 689
29.1 Introduction......Page 691
29.2 Types of Biclusters......Page 692
29.3 Groups of Biclusters......Page 693
29.4 Evaluation Functions......Page 694
29.5 Systematic and Stochastic Biclustering Algorithms......Page 696
29.6 Biological Validation......Page 699
References......Page 701
30.1 Introduction......Page 705
30.2 Condition-Specific Pathway Identification......Page 706
30.2.1 Gene Set Analysis......Page 707
30.2.2 Condition-Specific Pathway Inference......Page 711
30.3 Disease Gene Prioritization and Genetic Pathway Detection......Page 721
30.4 Module Networks......Page 724
References......Page 725
31.1 Introduction......Page 731
31.2 Notations......Page 732
31.3 Differential Mean of Expression......Page 734
31.3.1 Single Factor Differential Expression......Page 735
31.3.2 Multifactor Differential Expression......Page 737
31.3.3 Empirical Bayes Extension......Page 738
31.4.1 F-Test for Two-Group Differential Variability Analysis......Page 739
31.4.2 Bartlett’s and Levene’s Tests for Multigroup Differential Variability Analysis......Page 740
31.5.1 Gaussian Mixture Model (GMM) for Finite Levels of Expression......Page 741
31.5.2 Outlier Detection Strategy......Page 743
31.5.3 Kurtosis Excess......Page 744
31.6 Differential Expression by Chromosomal Aberrations: The Local Properties......Page 745
31.6.1 Wavelet Variance Scanning (WAVES) for Single-Sample Analysis......Page 748
31.6.2 Local Singular Value Decomposition (LSVD) for Compendium of Tumors......Page 749
31.6.3 Locally Adaptive Statistical Procedure (LAP) for Compendium of Tumors with Control Samples......Page 750
31.7.1 Friendly Neighbors Algorithm: A Multiplicative Interactome......Page 751
31.7.2 GeneRank: A Contributing Interactome......Page 752
31.7.3 Top Scoring Pairs (TSP): A Differential Interactome......Page 753
31.8 Differential Coexpression: Global MultiDimensional Interactome......Page 754
31.8.1 Kostka and Spang’s Differential Coexpression Algorithm......Page 755
31.8.3 Differential Friendly Neighbors (DiffFNs)......Page 758
References......Page 760
VI ANALYSIS OF GENOMES......Page 763
32.1 Introduction......Page 765
32.3 Ortholog Assignment......Page 767
32.3.1 Sequence Similarity-Based Method......Page 769
32.3.2 Phylogeny-Based Method......Page 771
32.3.3 Rearrangement-Based Method......Page 772
32.4 Gene Cluster and Synteny Detection......Page 774
32.4.1 Synteny Detection......Page 776
32.4.2 Gene Cluster Detection......Page 779
References......Page 783
33.1 Introduction......Page 789
33.2 Preliminaries......Page 792
33.3 Sorting by Reversals......Page 793
33.3.1 Approaches to Approximation Algorithms......Page 794
33.3.2 Signed Permutations......Page 797
33.4 Sorting by Transpositions......Page 799
33.4.1 Approximation Results......Page 800
33.5.1 Sorting by Prefix Reversals......Page 801
33.5.3 Sorting by Block Interchange......Page 802
33.6 Sorting by More Than One Operation......Page 803
33.6.1 Unified Operation: Doule Cut and Join......Page 804
33.7 Future Research Directions......Page 805
33.8 Notes on Software......Page 806
References......Page 807
34.1.1 What this Chapter is About......Page 813
34.1.2 Definitions and Notations......Page 814
34.2.1 Brief Introduction......Page 815
34.2.2 The Context and the Problems......Page 816
34.2.3 Common Intervals in Permutations and the Commuting Generators Strategy......Page 818
34.2.4 Conserved Intervals in Permutations and the Bound-and-Drop Strategy......Page 822
34.2.5 Common Intervals in Strings and the Element Plotting Strategy......Page 823
34.3.1 Introduction and Definition of the Problems......Page 825
34.3.2 An Approximation Algorithm for BAL-FMB......Page 827
34.3.3 An Exact Algorithm for UNBAL-FMB.......Page 831
34.4 Conclusion......Page 835
References......Page 836
35.1 Introduction......Page 839
35.2.1 Preliminary Remarks on DNA......Page 842
35.2.2 Indicator Function......Page 843
35.2.3 Representation......Page 846
35.2.4 Representation Models......Page 847
35.2.5 Constraints on the Representation in R2......Page 848
35.2.7 DNA Walks......Page 850
35.3.1 Long-Range Correlation......Page 852
35.3.2 Power Spectrum......Page 854
35.3.3 Complexity......Page 857
35.4 Wavelet Analysis......Page 858
35.4.2 Haar Series......Page 859
35.4.3 Discrete Haar Wavelet Transform......Page 861
35.5 Haar Wavelet Coefficients and Statistical Parameters......Page 863
35.6 Algorithm of the Short Haar Discrete Wavelet Transform......Page 866
35.7 Clusters of Wavelet Coefficients......Page 868
35.7.1 Cluster Analysis of the Wavelet Coefficients of the Complex DNA Representation......Page 870
35.7.2 Cluster Analysis of the Wavelet Coefficients of DNA Walks......Page 874
35.8 Conclusion......Page 878
References......Page 879
36.1 Introduction......Page 883
36.2 Problem Statement and Notations......Page 884
36.3.1 Clark’s Inference Rule......Page 886
36.3.2 Pure Parsimony Model......Page 888
36.3.3 Phylogeny Methods......Page 889
36.4.1 Maximum Likelihood Methods......Page 891
36.4.3 Markov Chain Methods......Page 892
36.5 Pedigree Methods......Page 893
36.5.2 Zero Recombinant Haplotype Configurations......Page 894
36.5.3 Statistical Methods......Page 895
36.6.1 Evaluation Measurements......Page 896
36.6.3 Datasets......Page 897
36.7 Discussion......Page 898
References......Page 899
VII ANALYSIS OF BIOLOGICAL NETWORKS......Page 905
37.1.1 Predicting Biological Processes: A Major Challenge to Understanding Biology......Page 907
37.1.2 Historical Perspective and Mathematical Preliminaries of Networks......Page 908
37.1.3 Structural Properties of Biological Networks......Page 910
37.1.4 Local Topology of Biological Networks: Functional Motifs, Modules, and Communities......Page 913
37.2.1 Protein-Protein Interaction Networks......Page 918
37.2.2 Metabolic Networks......Page 919
37.2.3 Transcriptional Networks......Page 921
37.2.4 Other Biological Networks......Page 923
37.3.1 Biological Network Dynamic and Evolution......Page 924
37.3.2 Biological Networks and Disease......Page 926
Acknowledgments......Page 927
References......Page 928
38 PROBABILISTIC APPROACHES FOR INVESTIGATING BIOLOGICAL NETWORKS......Page 933
38.1 Probabilistic Models for Biological Networks......Page 934
38.1.1 Boolean Networks......Page 935
38.1.2 Probabilistic Boolean Networks: A Natural Extension......Page 940
38.1.3 Inferring Probabilistic Models from Experiments......Page 941
38.2.1 Dynamical Analysis and Temporal Properties......Page 942
38.2.2 Impact of Update Strategies for Analyzing Probabilistic Boolean Networks......Page 945
38.2.3 Simulations of a Probabilistic Boolean Network......Page 946
References......Page 951
39.1 Introduction......Page 955
39.2.1 Model Checking......Page 956
39.2.2 SPIN and Promela......Page 957
39.2.3 LTL......Page 958
39.3.2 A Case Study......Page 959
39.3.3 Translating Boolean Regulatory Graphs into Promela......Page 961
39.3.4 Some Results......Page 962
39.3.6 Related Work and Bibliographic Notes......Page 964
39.4 Probabilistic Model Checking for Biological Systems......Page 965
39.4.1 Motivation and Background......Page 966
39.4.2 A Kinetic Model of mRNA Translation......Page 967
39.4.3 Probabilistic Model Checking......Page 968
39.4.4 The Prism Model......Page 969
39.4.5 Insertion Errors......Page 973
39.4.6 Concluding Remarks......Page 974
39.4.7 Related Work and Bibliographic Notes......Page 975
References......Page 976
40.1 Introduction......Page 981
40.2 Reverse-Engineering of Biological Networks......Page 982
40.2.1 Evaluation of the Performance of Reverse-Engineering Methods......Page 984
40.3 Classical Combinatorial Algorithms: A Case Study......Page 986
40.3.1 Benchmarking RE Combinatorial-Based Methods......Page 987
40.3.2 Software Availability......Page 990
References......Page 991
41.1 Introduction......Page 995
41.2 Gene Networks: Definition and Properties......Page 996
41.3 Gene Expression: Data and Analysis......Page 998
41.5 Correlation-Based Methods......Page 999
41.6 Probabilistic Graphical Models......Page 1001
41.7 Constraint-Based Data Mining......Page 1003
41.7.1 Multiple Usages of Extracted Patterns......Page 1005
41.7.2 Mining Gene Regulation from Transcriptome Datasets......Page 1006
41.8 Validation......Page 1009
41.8.1 Statistical Validation of Network Inference......Page 1010
41.8.2 Biological Validation......Page 1012
41.9 Conclusion and Perspectives......Page 1013
References......Page 1014
42.1.1 miRNA-mediated Genetic Regulatory Networks......Page 1019
42.1.2 The Four Levels of Regulation in GRNs......Page 1021
42.2 Fundamental Component Interaction Research: Predicting miRNA Genes, Regulators, and Targets......Page 1022
42.2.1 Prediction of Novel miRNA Genes......Page 1023
42.2.3 Prediction of miRNA Transcript Elements and Transcriptional Regulation......Page 1024
42.3.2 Reverse Engineering—Inference of MicroRNA Modules Using Top-Down Approaches......Page 1028
42.4.1 Global Architecture Properties of miRNA-mediated Post-transcriptional Networks......Page 1033
42.4.2 Local Architecture Properties of miRNA-mediated Post-transcriptional Networks......Page 1034
References......Page 1041
INDEX......Page 1047