Contents -- Preface -- Part 1 Surveys of Selected Topics -- 1. Fixed-Parameter Algorithms for Graph-Modeled Data Clustering F. Hüffner, R. Niedermeier and S. Wernicke -- 1.1. Introduction -- 1.2. Fixed-Parameter Tractability Basics and Techniques -- 1.2.1. Kernelizations -- 1.2.1.1. An Introductory Example -- 1.2.1.2. The Kernelization Concept -- 1.2.2. Depth-Bounded Search Trees -- 1.3. CaseStudies fromGraph-ModeledDataClustering -- 1.3.1. Clique -- 1.3.1.1. Finding Maximum Cardinality Cliques -- 1.3.1.2. Enumerating Maximal Cliques -- 1.3.2. Cluster Editing -- 1.3.3. Clique Cover -- 1.4. Conclusion -- 1.4.1. Practical Guidelines -- 1.4.2. Challenges -- References -- 2. Probabilistic Distance Clustering: Algorithm and Applications C. Iyigun and A. Ben-Israel -- 2.1. Introduction -- 2.2. Probabilistic {d,q}-Clustering -- 2.2.1. Probabilities -- 2.2.2. The Joint Distance Function -- 2.2.3. An Extremal Principle -- 2.2.4. An Extremal Principle for the Cluster Sizes -- 2.2.5. Centers -- 2.2.6. The Centers and the Joint Distance Function -- 2.3. ThePDQAlgorithm -- 2.4. Estimation of Parameters of Normal Distribution -- 2.4.1. A Comparison of the PDQ Algorithm (Algorithm 1) and the EM Method (Algorithm 2) -- 2.5. Numerical Experiments -- 2.6. Multi-Facility Location Problems -- 2.6.1. Fermat-Weber Location Problem -- 2.6.2. Multiple Facility Location Problem -- 2.7. Determining the "Right"Number of Clusters -- References -- 3. Analysis of Regulatory and Interaction Networks from Clusters of Co-expressed Genes E. Yang, A. Misra, T. J. Maguire and I. P. Androulakis -- 3.1. Identification of Intervention Targets: Regulatory and Interaction Networks -- 3.1.1. Identification of Informative Temporal Expression Patterns -- 3.2. Analysis of Regulatory Networks -- 3.2.1. Expression Data -- 3.2.2. Regulatory Network Construction and Analysis.

3.3. Analysis of InteractionNetworks -- 3.3.1. Expression Data -- 3.3.2. Interaction Network Construction and Analysis -- 3.4. Intervention Strategies -- Acknowledgements -- References -- 4. Graph-based Approaches for Motif Discovery E. Zaslavsky -- 4.1. Introduction -- 4.2. Graph-Theoretic Formulation -- 4.3. Linear Programming-based Algorithms -- 4.3.1. Edge-Modeling Formulation -- 4.3.1.1. Graph Pruning -- 4.3.2. Cost-Aggregating Formulation -- 4.4. Maximum Density Subgraph-based Algorithm -- 4.5. Subtle Motif Algorithms -- 4.5.1. Winnowing Techniques -- 4.5.2. Clique Finding with Consensus Constraint -- 4.6. Discussion -- Acknowledgements -- References -- 5. Statistical Clustering Analysis: An Introduction H. Zhang -- 5.1. Introduction -- 5.2. Similarity (Dissimilarity) Measures -- 5.2.1. Measures for Observation Clustering -- 5.2.1.1. Euclidean Distance and Minkowski Distance -- 5.2.1.2. Mahalanobis Distance -- 5.2.1.3. Cosine -- 5.2.2. Measures for Variable Clustering -- 5.2.2.1. Pearson's Correlation Coefficient -- 5.2.2.2. Mutual Information -- 5.3. Clustering Algorithm -- 5.3.1. K-Means Algorithm -- 5.3.2. E-M Algorithm -- 5.3.3. Hierarchical Clustering -- 5.3.4. Self-Organizing Map -- 5.4. Determining the Number of Clusters -- 5.4.1. Model-based Method -- 5.4.2. Scale-based Method -- References -- Part 2 New Methods and Applications -- 6. Diversity Graphs P. Blain, C. Davis, A. Holder, J. Silva and C. Vinzant -- 6.1. Introduction -- 6.2. Notation, Definitions and Preliminary Results -- 6.3. Graphs That Support Diversity -- 6.4. Algorithms and Solutions for the Pure Parsimony Problem -- 6.5. Directions for Future Research -- References -- 7. Identifying Critical Nodes in Protein-Protein Interaction Networks V. Boginski and C. W. Commander -- 7.1. Introduction -- 7.2. Protein-Protein Interaction Networks.

7.3. Optimization Approaches for Critical Node Detection -- 7.3.1. The Critical Node Detection Problem -- 7.3.2. Cardinality Constrained Problem -- 7.4. Heuristic Approaches for Critical Node Detection -- 7.4.1. Multi-Start Combinatorial Heuristic -- 7.4.2. Genetic Algorithms -- 7.5. Computational Experiments -- 7.6. Conclusions -- References -- 8. Faster Algorithms for Constructing a Concept (Galois) Lattice V. Choi -- 8.1. Introduction -- 8.2. Background and Terminology on FCA -- 8.3. BasicProperties -- 8.3.1. Defining the Equivalence Classes -- 8.3.2. Characterizations of Closure -- 8.4. Algorithm: Constructing a Concept/Galois Lattice -- 8.4.1. High-Level Idea -- 8.4.2. Implementation -- 8.4.2.1. Further Improvement: Dynamically Update Adjacency Lists -- 8.5. Variants of theAlgorithm -- 8.5.1. Algorithm 2: Computing All Concepts or Maximal Bipartite Cliques -- 8.5.2. Algorithm 3: Constructing a Closed Itemset Lattice -- 8.6. Discussion -- Acknowledgment -- References -- Appendix -- 9. A Projected Clustering Algorithm and Its Biomedical Application P. Deng, Q. Ma and W. Wu -- 9.1. Introduction -- 9.2. RelatedWorks -- 9.2.1. Density-based Algorithms -- 9.2.2. Distance-based Algorithms -- 9.3. The IPROCLUSAlgorithm -- 9.3.1. Modified Manhattan Segmental Distance -- 9.3.2. Initialization Phase -- 9.3.3. Iterative Phase -- 9.3.3.1. Simplified Replacing Logic -- 9.3.4. Refinement Phase -- 9.3.4.1. Dimension Tuning Process -- 9.4. EmpiricalResults -- 9.4.1. Synthetic Data Generation -- 9.4.2. Results on Synthetic Datasets -- 9.4.3. Results on the Colon Tumor Dataset -- 9.5. Conclusion -- References -- 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 and M. A. Langston -- 10.1. Overview -- 10.2. Description ofData.

10.3. Correlation Computations -- 10.4. Clique and Its Variants -- 10.5. Statistical Evaluation and Biological Relevance -- 10.6. ProteomicData Integration -- 10.7. Remarks -- Acknowledgments -- References -- 11. A Novel Similarity-based Modularity Function for Graph Partitioning Z. Feng, X. Xu, N. Yuruk and T. Schweiger -- 11.1. Introduction -- 11.2. RelatedWork -- 11.3. A Novel Similarity-based Modularity -- 11.4. A Genetic Graph Partitioning Algorithm -- 11.5. AFastAgglomerativeAlgorithm -- 11.6. EvaluationResults -- 11.6.1. Tests on Synthetic Graphs -- 11.6.2. Real Applications -- 11.7. Conclusion -- References -- 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 and J. E. Perez-Ortin -- 12.1. Introduction -- 12.2. Materials and Data Acquisition -- 12.2.1. Glucose-Galactose Shift Experiments -- 12.2.2. Measuring Transcription Rates (TR) Using the Genomic Run-on (GRO) Method -- 12.2.3. Measuring mRNA or Transcript Levels (TL) -- 12.2.4. The TL-TR Plots -- 12.3. StatisticalAnalysis -- 12.3.1. Calibration of TL Data -- 12.3.2. Calibration of TR Data -- 12.3.3. Kinetic Analysis of the Changes in mRNA Levels -- 12.3.4. Transcript-Degradation to Transcription (D/T) Ratios -- 12.4. Experimental Results -- 12.5. Conclusion and Discussion -- Acknowledgments -- References -- 13. The Complexity of Feature Selection for Consistent Biclustering O. E. Kundakcioglu and P. M. Pardalos -- 13.1. Introduction -- 13.2. Consistent Biclustering -- 13.3. Complexity Results -- 13.4. Closing Remarks -- References -- 14. Clustering Electroencephalogram Recordings to Study Mesial Temporal Lobe Epilepsy C.-C. Liu, W. Suharitdamrong, W. A. Chaovalitwongse, G. A. Ghacibeh and P. M. Pardalos -- 14.1. Introduction -- 14.2. Epilepsy as aDynamicalBrainDisorder.

14.3. Data Information -- 14.4. Graph-TheoreticModeling forBrainConnectivity -- 14.4.1. Cross-Mutual Information (CMI) -- 14.4.2. Maximum Clique Algorithm -- 14.5. Results -- 14.6. Conclusion and Discussion -- Acknowledgment -- References -- 15. Relating Subjective and Objective Pharmacovigilance Association Measures R. K. Pearson -- 15.1. Introduction -- 15.2. Aggregate Associations -- 15.3. Subjective Associations -- 15.4. Case-Specific Associations -- 15.5. Relations between Measures -- 15.6. Clustering Drugs -- 15.6.1. The Case Study -- 15.6.2. The Clustering Approach -- 15.6.3. Summary of the Results -- 15.7. Interpreting the Clusters -- 15.8. Summary -- References -- 16. A Novel Clustering Approach: Global Optimum Search with Enhanced Positioning M. P. Tan and C. A. Floudas -- 16.1. Introduction -- 16.2. Methods -- 16.2.1. Experimental Data -- 16.2.2. Theoretical and Computational Framework -- 16.2.2.1. Notation -- 16.2.2.2. Hard Clustering by Global Optimization -- 16.2.2.3. The GOS Algorithm for Clustering -- 16.2.2.4. Determining the Optimal Number of Clusters -- 16.2.3. Proposed Algorithm -- 16.3. Results and Discussion -- 16.3.1. Description of Comparative Study -- 16.3.2. Intra-cluster Error Sum -- 16.3.3. Inter-cluster Error Sum -- 16.3.4. Difference between Intra-cluster and Inter-cluster Error Sums -- 16.3.5. Optimal Number of Clusters -- 16.3.6. Coherence and Biological Relevance -- 16.3.7. Additional Constraints for Large Datasets -- 16.4. Conclusion -- 16.5. Computational Resources -- Acknowledgements -- References -- Index.