MITACS Bioinformatics Series

The extent of human genetic variability mediated by large genomic (> 10kb) alterations is not fully understood. Recent technological development has led to the discovery of many such variations, with the distinct possibility that many more remain to be discovered. It is clear that understanding these variations, and their role in diseases (particularly cancer).

Many of the available technologies do well for detecting copy number variation, but other variation, like inversions and translocations remain hard to detect. Here, I will describe a number of (computational) approaches to identify these variations, focusing in particular on the identification of copy neutral variations. This includes mining of genotype data to detect inversions, the use of 'older' technologies like multiplex PCR, and BAC end-sequencing to detect fusion events, and algorithms for 'haplotype assembly' as a prelude to detecting structural variation.

Variation in human DNA sequences account for a significant amount of genetic risk factors for common disease such as hypertension, diabetes, Alzheimer's disease, and cancer. Identifying the human sequence variation that makes up the genetic basis of common disease will have a tremendous impact on medicine in many ways. Recent efforts to identify these genetic factors through large scale association studies which compare information on variation between a set of healthy and diseased individuals have been remarkably successful. However, despite the success of these initial studies, many challenges and open questions remain on how to design and analyze the results of association studies. In this talk, I will formulate association study design as an optimization problem where the goal is to design a study which maximizes the statistical power to detect genetic risk factors given a fixed budget. I will demonstrate how we can leverage the inherent correlation structure of variation in the human genome to design efficient association studies.

Eleazar Eskin obtained his Ph.D. in Computer Science from Columbia University in 2002. He is currently an Assistant Professor in the departments of Human Genetics and Computer Science at the University of California, Los Angeles. Previously he was an Assistant Professor in Residence at the University of California, San Diego.

The work discussed in this talk falls into the emerging area of Population Genomics. I will first introduce the area and then talk about specific problems and combinatorial algorithms involved in the inference of recombination from population data.

A phylogenetic network (or Ancestral Recombination Graph) is a generalization of a tree, allowing structural properties that are not tree-like. With the growth of genomic and population data (coming for example from the HAPMAP project) much of which does not fit ideal tree models, and the increasing appreciation of the genomic role of such phenomena as recombination (crossing-over and gene-conversion), recurrent and back mutation, horizontal gene transfer, and mobile genetic elements, there is greater need to understand the algorithmics and combinatorics of phylogenetic networks.

In this talk I will survey a range of our recent algorithmic and mathematical results on phylogenetic networks with recombination and show applications of these results to several issues in Population Genomics: Association Mapping; Finding Recombination Hotspots in genotype sequences; Imputing the values of missing haplotype data; Determining the extent of recombination in the evolution of LPL sequences; Distinguishing the role of crossing-over from gene-conversion in Arabidopsis; Characterizing some aspects of the haplotypes produced by the program PHASE; Studying the effect of using genotype data in place of haplotype data, imputing missing data, finding optimal recombination mosaics etc.

Various parts of this work are joint work with Satish Eddhu, Chuck Langley, Dean Hickerson, Yun S. Song, Yufeng Wu, V. Bansal, V. Bafna and Z. Ding.

Professor Gusfield's background is in Combinatorial Optimization, and various applications of Combinatorial Optimization. He has worked extensively on problems of network flow, matroid optimization, statistical data security, stable marriage and matching, string algorithms and sequence analysis, phylogenetic tree inference, haplotype inference, and inference of phylogenetic networks with homoplasy and recombination. He received his Ph.D. in 1980 from UC Berkeley, working with Richard Karp, and was an Assistant Professor at Yale University from 1980 to 1986.

Professor Gusfield moved to UC Davis in July 1986. Since then, he has mostly addressed problems in Computational Biology and Bioinformatics. He first addressed questions about building evolutionary trees, and then problems in molecular sequence analysis. He presently focuses mostly on optimization problems related to population genetics and population-scale genomics. Two particular problems are haplotype inference and inferences about historical recombination. His main support for work on computational biology and bioinformatics came initially from the Department of Energy Human Genome Project through the Lawrence Berkeley Labs Human Genome Center, then directly from DOE Human Genome Project, but since then his work in computational biology has been funded by the NSF. His book, "Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology" has helped to define the intersection of computer science and computational biology. It has been translated into Russian, and a South Asian edition has recently been published. Professor Gusfield serves on the editorial boards of the Journal of Computational Biology, and SIAM J. on Computing, and is the founding Editor-in-Chief of The IEEE/ACM Transactions on Computational Biology and Bioinformatics. Other notable service to the Computational Biology community consists of serving as Program Chair for the 2004 RECOMB conference.

At UCD, Professor Gusfield was chair of the Computer Science Department for four years, and wrote the bioinformatics section (one of three) of the Genomics/Bioinformatics initiative proposal that resulted in the creation of the UCD Genomics Center (which has hired 17 new faculty), and continues to serve on its internal Steering committee. He is currently co-chair of the UCD campus initiative on "Computational Characterization and Exploitation of Biological Networks" (see cnb.ucdavis.edu), which plans to hire seven new faculty in this area over the next three years.

This talk overviews the past and current state of a selected part of the emerging research area of the field of biomolecular devices. We particularly emphasize molecular devices that are:

• Autonomous: executing steps with no exterior mediation after starting, and
• Programmable: the tasks executed can be modified without entirely redesigning the nanostructure.

We discuss work in this area that makes use of synthetic DNA to self-assemble into DNA nanostructure devices. Recently, there have been a series of quite astonishing experimental results - which have taken the technology from a state of intriguing possibilities into demonstrated capabilities of quickly increasing scale. We discuss various such programmable molecular-scale devices that achieve:

• computation,
• 2D patterning, and
• transport.

This talk will presented for a computer science audience, and particularly emphasizes the unique impact of computer science to this quickly evolving and interdisciplinary field. Papers (see survey papers 44 & 45) discussed can be downloaded from URL: http://www.cs.duke.edu/~reif/vita/topics/biomolecular.html

John Reif is Hollis Edens Distinguished Professor in Trinity College of Arts and Sciences at Duke University since 2003 and Professor of Computer Science at Duke University since 1986. Previously he was Associate Professor, Harvard University. He received a Ph.D. Applied Mathematics in 1977 from Harvard University, an M.S. Applied Mathematics in 1975 from Harvard University and was awarded a magna cum laude B.S. in Applied Mathematics & Compute Science in 1973 from Tufts University. He is Fellow of the Association for the Advancement of Science (AAAS) since 2003, Fellow of IEEE since 1993, Fellow of ACM since 1996, and Fellow of Inst. of Combinatorics since 1991. He is the author of over 200 papers and has edited three books on synthesis of parallel and randomized algorithms. His homepage (with downloadable vita and papers) is at www.cs.duke.edu/~reif. Although originally primarily a theoretical computer scientist, he also has made a number of contributions to practical areas of computer science including parallel architectures, data compression, robotics, and optical computing. He has also worked for many years on the development and analysis of parallel algorithms for various fundamental problems including the solution of large sparse systems, sorting, graph problems, data compression, and a wide range of efficient parallel algorithms using randomization. He has developed algorithms and lower bounds for a large variety of robotic motion planning problems, and provided the first known computational complexity results for a robotic motion-planning problem. In the last decade Reif has concentrated on DNA computing, nanostructures, and molecular robotics, with papers in PNAS, Science, and Nature on laboratory demonstrations of novel DNA nanostructures known as TX and Crossover tiles, the first molecular-scale computations via DNA tiling assembly, the first autonomous DNA robot that traversed a DNA nanostructure, and very large searchable memories constructed of DNA. His papers (see survey papers 44 & 45) on these topics are at: http://www.cs.duke.edu/~reif/vita/topics/biomolecular.html.
He is also President of Eagle Eye, Inc., which specializes in defense and medical applications of DNA biotechnology, and has developed an isothermal exquisitely sensitive DNA detection method with colorimetic output.

Protein motions, ranging from molecular flexibility to large-scale conformational change, play an essential role in many biochemical processes. For example, some devastating diseases such as Alzheimer's and bovine spongiform encephalopathy (Mad Cow) are associated with the misfolding of proteins. Despite the explosion in our knowledge of structural and functional data, our understanding of protein movement is still very limited because it is difficult to measure experimentally and computationally expensive to simulate.

In this talk we describe a method we have developed for modeling protein motions that is based on probabilistic roadmap methods (PRM) for motion planning. Our technique yields an approximate map of a protein's potential energy landscape and can be used to generate transitional motions of a protein to the native state from unstructured conformations or between specified conformations. We describe a method based on rigidity theory that allows us to sample conformation space more efficiently than our initial sampling strategy and enables us to study a broader range of motions for larger proteins and new analysis tools that enable us to extract kinetics information, such as folding rates. For example, we show how our map-based tools for modeling and analyzing folding landscapes can capture subtle folding differences between protein G and its mutants, NuG1 and NuG2. In recent work, we have applied our techniques to identify and study the folding core. More information regarding our work, including an archive of protein motions generated with our technique, are available from our protein folding server: http://parasol.tamu.edu/foldingserver/

Nancy M. Amato is a professor of computer science at Texas A&M University. She received B.S. and A.B. degrees in Mathematical Sciences and Economics, respectively, from Stanford University, and M.S. and Ph.D. degrees in Computer Science from UC Berkeley and the University of Illinois at Urbana-Champaign, respectively. She was an AT&T Bell Laboratories PhD Scholar, she is a recipient of a CAREER Award from the National Science Foundation, and she is a Distinguished Lecturer for the IEEE Robotics and Automation Society. She served as an Associate Editor of the IEEE Transactions on Robotics and Automation and of the IEEE Transactions on Parallel and Distributed Systems, she serves on review panels for NIH and NSF, and she regularly serves on conference organizing and program committees. She is a member of the Computing Research Association's Committee on the Status of Women in Computing Research (CRA-W) and she co-directs the CRA-W's Distributed Mentor Program (http://www.cra.org/Activities/craw/dmp/). Her main areas of research focus are motion planning, computational biology and geometry, and high-performance computing. Current projects include the development of a new technique for approximating protein folding pathways and energy landscapes, and STAPL, a parallel C++ library enabling the development of efficient, portable parallel programs. More information regarding our work can be found at http://parasol.tamu.edu/

Not available yet.