Genome-Scale Computational Approaches to Memory-Intensive Applications in Systems Biology Session: Bioscience Event Type: Paper Time: 2:30pm - 3:00pm Session Chair: Srinivas Aluru Speaker(s): Yun Zhang, Faisal N. Abu-Khzam, Nicole E. Baldwin, Elissa J. Chesler, Michael A. Langston, Nagiza F. Samatova Location: 602-604 Abstract: Effective graph-theoretical approaches for small biological networks are not computationally feasible for genome-scale analysis. These systems biological problems are typically NP-hard, with exponential run times for finding optimal solutions. Plus they are memory-intensive, requiring effective data sharing across many processors. For example, enumeration of maximal cliques, essential to many biological applications, can yield 3^(n/3) maximal cliques for a graph with n vertices. Memory requirements reach terabyte scales even for modest-sized problems. Emerging hardware architectures with ultra-large globally addressable memory including the SGI Altix and Cray X1 are ideal for data-intensive problems. This paper presents a novel framework providing exact, parallel and scalable solutions to graph-theoretical biological network analysis. The framework exploits large-memory architectures by creating globally addressable bitmap memory indices with high compression rates, fast bitwise-logical operations, and reduced search space. Theoretical advances in fixed-parameter tractability augment performance for computationally feasible solutions to large combinatorial problems of systems biology. This paper can be found in the ACM and IEEE Digital Libaries Click here for ACM Click here for IEEE Chair/Speaker Details: Srinivas Aluru (Chair) Iowa State University Yun Zhang Department of Computer Science, University of Tennessee, Knoxville, TN 37996-3450, USA Faisal N. Abu-Khzam Division of Computer Science and Mathematics, Lebanese American University, Chouran, Beirut, Lebanon Nicole E. Baldwin Computational Biology Institute, Oak Ridge National Laboratory, P.O. Box 2008, Oak Ridge, TN 37831, USA Elissa J. Chesler Department of Anatomy and Neurobiology, University of Tennessee, Memphis, TN 38163, USA Michael A. Langston Department of Computer Science, University of Tennessee, Knoxville, TN 37996-3450, USA Nagiza F. Samatova Computational Biology Institute, Oak Ridge National Laboratory, P.O. Box 2008, Oak Ridge, TN 37831, USA