Parallel computing for bioinformatics and computational biology : models, enabling technologies, and case studies / edited by Albert Y. Zomaya.

Format:

Book

Contributor:

Zomaya, Albert Y.

Engineering Book Fund.

Series:

Wiley series on parallel and distributed computing

Language:

English

Subjects (All):

Bioinformatics.

Computational biology.

Parallel processing (Electronic computers).

Computational Biology.

Electronic Data Processing--methods.

Models, Biological.

Computer Simulation.

Medical Subjects:

Computational Biology.

Electronic Data Processing--methods.

Models, Biological.

Computer Simulation.

Physical Description:

xxix, 782 pages : illustrations ; 25 cm.

Place of Publication:

Hoboken, N.J. : Wiley-Interscience, [2006]

Summary:

This publication enables readers to handle more complex bioinformatics applications and larger and richer data sets. As the editor clearly shows, using powerful parallel computing tools can lead to significant breakthroughs in deciphering genomes, understanding genetic disease, designing customized drug therapies, and understanding evolution.

A broad range of bioinformatics applications is covered with demonstrations on how each one can be parallelized to improve performance and gain faster rates of computation. Current parallel computing techniques and technologies are examined, including distributed computing and grid computing. Readers are provided with a mixture of algorithms, experiments, and simulations that provide not only qualitative but also quantitative insights into the dynamic field of bioinformatics.

Parallel Computing for Bioinformatics and Computational Biology is a contributed work that serves as a repository of case studies, collectively demonstrating how parallel computing streamlines difficult problems in bioinformatics and produces better results. Each of the chapters is authored by an established expert in the field and carefully edited to ensure a consistent approach and high standard throughout the publication.

Researchers, educators, and students in the field of bioinformatics will discover how highperformance computing can enable them to handle more complex data sets, gain deeper insights, and make new discoveries.

Contents:

Part I Algorithms and Models 1

1 Parallel and Evolutionary Approaches to Computational Biology / Nouhad J. Rizk 3

1.2 Bioinformatics 13

1.3 Evolutionary Computation Applied to Computational Biology 20

2 Parallel Monte Carlo Simulation of HIV Molecular Evolution in Response to Immune Surveillance / Jack da Silva 29

2.2 The Problem 30

2.3 The Model 32

2.4 Parallelization with MPI 39

2.5 Parallel Random Number Generation 43

2.6 Preliminary Simulation Results 46

2.7 Future Directions 52

3 Differential Evolutionary Algorithms for In Vivo Dynamic Analysis of Glycolysis and Pentose Phosphate Pathway in Escherichia coli / Christophe Chassagnole 59

3.2 Mathematical Model 61

3.3 Estimation of the Parameters of the Model 67

3.4 Kinetic Parameter Estimation by DE 69

3.5 Simulation and Results 70

3.6 Stability Analysis 73

3.7 Control Characteristic 73

4 Compute-Intensive Simulations for Cellular Models / K. Burrage 79

4.2 Simulation Methods for Stochastic Chemical Kinetics 81

4.3 Aspects of Biology - Genetic Regulation 92

4.4 Parallel Computing for Biological Systems 96

4.5 Parallel Simulations 100

4.6 Spatial Modeling of Cellular Systems 104

4.7 Modeling Colonies of Cells 109

5 Parallel Computation in Simulating Diffusion and Deformation in Human Brain / Ning Kang 121

5.2 Anisotropic Diffusion Simulation in White Matter Tractography 122

5.3 Brain Deformation Simulation in Image-Guided Neurosurgery 132

Part II Sequence Analysis and Microarrays 147

6 Computational Molecular Biology / Azzedine Boukerche 149

6.2 Basic Concepts in Molecular Biology 150

6.3 Global and Local Biological Sequence Alignment 152

6.4 Heuristic Approaches for Biological Sequence Comparison 158

6.5 Parallel and Distributed Sequence Comparison 161

7 Special-Purpose Computing for Biological Sequence Analysis / Bertil Schmidt 167

7.2 Hybrid Parallel Computer 169

7.3 Dynamic Programming Communication Pattern 172

7.4 Performance Evaluation 179

7.5 Future Work and Open Problems 185

7.6 Tutorial 188

8 Multiple Sequence Alignment in Parallel on a Cluster of Workstations / Amitava Datta 193

8.2 CLUSTAL W 194

8.3 Implementation 201

8.4 Results 207

9 Searching Sequence Databases Using High-Performance BLASTs / Xue Wu 211

9.2 Basic Blast Algorithm 212

9.3 Blast Usage and Performance Factors 214

9.4 High Performance BLASTs 215

9.5 Comparing BLAST Performance 221

9.6 UMD-BLAST 226

9.7 Future Directions 228

10 Parallel Implementations of Local Sequence Alignment: Hardware and Software / Vipin Chaudhary 233

10.2 Sequence Alignment Primer 235

10.3 Smith-Waterman Algorithm 240

10.4 FASTA 244

10.5 BLAST 245

10.6 HMMER - Hidden Markov Models 249

10.7 ClustalW 252

10.8 Specialized Hardware: FPGA 257

11 Parallel Computing in the Analysis of Gene Expression Relationships / Robert L. Martino 265

11.1 Significance of Gene Expression Analysis 265

11.2 Multivariate Gene Expression Relations 267

11.3 Classification Based on Gene Expression 274

11.4 Discussion and Future Directions 280

12 Assembling DNA Fragments with a Distributed Genetic Algorithm / Gabriel Luque 285

12.2 DNA Fragment Assembly Problem 286

12.3 DNA Fragment Assembly Using the Sequential GA 289

12.4 DNA Fragment Assembly Problem Using the Parallel GA 292

12.5 Experimental Results 294

13 A Cooperative Genetic Algorithm for Knowledge Discovery in Microarray Experiments / Mohammed Khabzaoui 303

13.2 Microarray Experiments 304

13.3 Association Rules 306

13.4 Multi-Objective Genetic Algorithm 308

13.5 Cooperative Multi-Objective Genetic Algorithm (PMGA) 313

13.6 Experiments 315

Part III Phylogenetics 325

14 Parallel and Distributed Computation of Large Phylogenetic Trees / Alexandros Stamatakis 327

14.2 Maximum Likelihood 330

14.3 State-of-the-Art ML Programs 332

14.4 Algorithmic Solutions in RAxML-III 334

14.5 HPC Solutions in RAxML-III 337

14.6 Future Developments 341

15 Phylogenetic Parameter Estimation on COWs / Ekkehard Petzold 347

15.2 Phylogenetic Tree Reconstruction using Quartet Puzzling 349

15.3 Hardware, Data, and Scheduling Algorithms 354

15.4 Parallelizing PEst 356

15.5 Extending Parallel Coverage in PEst 359

16 High-Performance Phylogeny Reconstruction Under Maximum Parsimony / Tiffani L. Williams 369

16.2 Maximum Parsimony 374

16.3 Exact MP: Parallel Branch and Bound 378

16.4 MP Heuristics: Disk-Covering Methods 381

16.5 Summary and Open Problems 390

Part IV Protein Folding 395

17 Protein Folding with the Parallel Replica Exchange Molecular Dynamics Method / Ruhong Zhou 397

17.2 REMD Method 399

17.3 Protein Folding with REMD 403

17.4 Protein Structure Refinement with REMD 420

18 High-Performance Alignment Methods for Protein Threading / R. Andonov 427

18.2 Formal Definition 431

18.3 Mixed Integer Programming Models 434

18.4 Divide-and-Conquer Technique 444

18.5 Parallelization 448

18.6 Future Research Directions 453

19 Parallel Evolutionary Computations in Discerning Protein Structures / Richard O. Day 459

19.2 PSP Problem 460

19.3 Protein Structure Discerning Methods 461

19.4 PSP Energy Minimization EAs 471

19.5 PSP Parallel EA Performance Evaluation 477

19.6 Results and Discussion 479

19.7 Conclusions and Suggested Research 483

Part V Platforms and Enabling Technologies 487

20 A Brief Overview of Grid Activities for Bioinformatics and Health Applications / Ali Al Mazari 489

20.2 Grid Computing 490

20.3 Bioinformatics and Health Applications 491

20.4 Grid Computing for Bioinformatics and Health Applications 491

20.5 Grid Activities in Europe 492

20.6 Grid Activities in the United Kingdom 494

20.7 Grid Activities in the USA 497

20.8 Grid Activities in Asia and Japan 498

20.9 International Grid Collaborations 499

20.10 International Grid Collaborations 499

20.11 Conclusions and Future Trends 500

21 Parallel Algorithms for Bioinformatics / Shahid H. Bokhari 509

21.2 Parallel Computer Architecture 511

21.3 Bioinformatics Algorithms on the Cray MTA System 517

22 Cluster and Grid Infrastructure for Computational Chemistry and Biochemistry / Kim K. Baldridge 531

22.2 GAMESS Execution on Clusters 532

22.3 Portal Technology 537

22.4 Running GAMESS with Nimrod Grid-Enabling Infrastructure 538

22.5 Computational Chemistry Workflow Environments 542

23 Distributed Workflows in Bioinformatics / Arun Krishnan 551

23.2 Challenges of Grid Computing 553

23.3 Grid Applications 554

23.4 Grid Programming 555

23.5 Grid Execution Language 557

23.6 GUI-Based Workflow Construction and Execution 565

24 Molecular Structure Determination on a Computational and Data Grid / Russ Miller 583

24.2 Molecular Structure Determination 585

24.3 Grid Computing in Buffalo 586

24.4 Center for Computational Research 588

24.5 ACDC-Grid Overview 588

24.6 Grid Research Collaborations 596

24.7 Grid Research Advancements 601

24.8 Grid Research Application Abstractions and Tools 603

25 GIPSY: A Problem-Solving Environment for Bioinformatics Applications / Rajendra R. Joshi 623

25.2 Architecture 626

25.3 Currently Deployed Applications 634

26 TaskSpaces: A Software Framework for Parallel Bioinformatics on Computational Grids / Hans De Sterck 651

26.2 The TaskSpaces Framework 655

26.3 Application: Finding Correctly Folded RNA Motifs 661

26.4 Case Study: Operating the Framework on a Computational Grid 663

26.5 Results for the RNA Motif Problem 664

26.6 Future Work 668

27 The Organic Grid: Self-Organizing Computational Biology on Desktop Grids / Arjav J.

Chakravarti 671

27.2 Background and Related Work 674

27.3 Measurements 686

27.5 Future Directions 699

28 FPGA Computing in Modern Bioinformatics / H. Simmler 705

28.1 Parallel Processing Models 706

28.2 Image Processing Task 708

28.3 FPGA Hardware Accelerators 711

28.4 Image Processing Example 716

28.5 Case Study: Protein Structure Prediction 720

29 Virtual Microscopy: Distributed Image Storage, Retrieval, Analysis, and Visualization / T. Pan 737

29.2 Architecture 738

29.3 Image Analysis 747

29.4 Clinical Use 752

29.5 Education 755

29.6 Future Directions 756.

Notes:

Includes bibliographical references and index.

Local Notes:

Acquired for the Penn Libraries with assistance from the Engineering Book Fund.

ISBN:

0471718483

OCLC:

60189471

Publisher Number:

9780471718482

Online:

Publisher description