Table of Contents
Preface vii
Part 1 Surveys of Selected Topics 1
1 Fixed-Parameter Algorithms for Graph-Modeled Data Clustering F. Huffner R. Niedermeier S. Wernicke 3
1.1 Introduction 4
1.2 Fixed-Parameter Tractability Basics and Techniques 6
1.3 Case Studies from Graph-Modeled Data Clustering 12
1.4 Conclusion 22
References 24
2 Probabilistic Distance Clustering: Algorithm and Applications C. Iyigun A. Ben-Israel 29
2.1 Introduction 29
2.2 Probabilistic {d,q}-Clustering 31
2.3 The PDQ Algorithm 38
2.4 Estimation of Parameters of Normal Distribution 40
2.5 Numerical Experiments 42
2.6 Multi-Facility Location Problems 46
2.7 Determining the "Right" Number of Clusters 50
References 51
3 Analysis of Regulatory and Interaction Networks from Clusters of Co-expressed Genes E. Yang A. Misra T. J. Maguire I. P. Androulakis 53
3.1 Identification of Intervention Targets: Regulatory and Interaction Networks 54
3.2 Analysis of Regulatory Networks 59
3.3 Analysis of Interaction Networks 69
3.4 Intervention Strategies 75
References 76
4 Graph-based Approaches for Motif Discovery E. Zaslavsky 83
4.1 Introduction 83
4.2 Graph-Theoretic Formulation 86
4.3 Linear Programming-based Algorithms 88
4.4 Maximum Density Subgraph-based Algorithm 92
4.5 Subtle Motif Algorithms 93
4.6 Discussion 95
References 96
5 Statistical Clustering Analysis: An Introduction H. Zhang 101
5.1 Introduction 101
5.2 Similarity (Dissimilarity) Measures 103
5.3 Clustering Algorithm 109
5.4 Determining the Number of Clusters 119
References 125
Part 2 New Methods and Applications 127
6 Diversity Graphs P. Blain C. Davis A. Holder J. Silva C. Vinzant 129
6.1Introduction 130
6.2 Notation, Definitions and Preliminary Results 130
6.3 Graphs That Support Diversity 135
6.4 Algorithms and Solutions for the Pure Parsimony Problem 140
6.5 Directions for Future Research 149
References 150
7 Identifying Critical Nodes in Protein-Protein Interaction Networks V. Boginski C. W. Commander 153
7.1 Introduction 153
7.2 Protein-Protein Interaction Networks 154
7.3 Optimization Approaches for Critical Node Detection 155
7.4 Heuristic Approaches for Critical Node Detection 158
7.5 Computational Experiments 160
7.6 Conclusions 165
References 165
8 Faster Algorithms for Constructing a Concept (Galois) Lattice V. Choi 169
8.1 Introduction 169
8.2 Background and Terminology on FCA 172
8.3 Basic Properties 173
8.4 Algorithm: Constructing a Concept/Galois Lattice 176
8.5 Variants of the Algorithm 179
8.6 Discussion 181
References 182
Appendix 185
9 A Projected Clustering Algorithm and Its Biomedical Application P. Deng Q. Ma W. Wu 187
9.1 Introduction 188
9.2 Related Works 190
9.3 The IPROCLUS Algorithm 192
9.4 Empirical Results 199
9.5 Conclusion 204
References 205
10 Graph Algorithms for Integrated Biological Analysis, with Applications to Type 1 Diabetes Data J. D. Eblen I. C. Gerling A. M. Saxton J. Wu J. R. Snoddy M. A. Langston 207
10.1 Overview 208
10.2 Description of Data 209
10.3 Correlation Computations 210
10.4 Clique and Its Variants 210
10.5 Statistical Evaluation and Biological Relevance 213
10.6 Proteomic Data Integration 215
10.7 Remarks 219
References 220
11 A Novel Similarity-based Modularity Function for Graph Partitioning Z. Feng X. Xu N. Yuruk T. Schweiger 223
11.1 Introduction 223
11.2 Related Work 225
11.3 A Novel Similarity-based Modularity 227
11.4 A Genetic Graph Partitioning Algorithm 229
11.5 A Fast Agglomerative Algorithm 230
11.6 Evaluation Results 231
11.7 Conclusion 235
References 235
12 Mechanism-based Clustering of Genome-wide RNA Levels: Roles of Transcription and Transcript-Degradation Rates S. Ji W. A. Chaovalitwongse N. Fefferman W. Yoo J. E. Perez-Ortin 237
12.1 Introduction 238
12.2 Materials and Data Acquisition 240
12.3 Statistical Analysis 242
12.4 Experimental Results 247
12.5 Conclusion and Discussion 251
References 253
13 The Complexity of Feature Selection for Consistent Biclustering O. E. Kundakcioglu P. M. Pardalos 257
13.1 Introduction 257
13.2 Consistent Biclustering 259
13.3 Complexity Results 263
13.4 Closing Remarks 265
References 265
14 Clustering Electroencephalogram Recordings to Study Mesial Temporal Lobe Epilepsy C.-C. Liu W. Suharitdamrong W. A. Chaovalitwongse G. A. Ghacibeh P. M. Pardalos 267
14.1 Introduction 268
14.2 Epilepsy as a Dynamical Brain Disorder 269
14.3 Data Information 270
14.4 Graph-Theoretic Modeling for Brain Connectivity 270
14.5 Results 276
14.6 Conclusion and Discussion 278
References 278
15 Relating Subjective and Objective Pharmacovigilance Association Measures R. K. Pearson 281
15.1 Introduction 281
15.2 Aggregate Associations 282
15.3 Subjective Associations 286
15.4 Case-Specific Associations 287
15.5 Relations between Measures 288
15.6 Clustering Drugs 290
15.7 Interpreting the Clusters 298
15.8 Summary 302
References 305
16 A Novel Clustering Approach: Global Optimum Search with Enhanced Positioning M. P. Tan C. A. Floudas 307
16.1 Introduction 308
16.2 Methods 310
16.3 Results and Discussion 320
16.4 Conclusion 327
16.5 Computational Resources 327
References 328
Index 333
