Bioinformatics FTE Proposal - Jan. 4, 1999; revised Jan. 28; and Feb. 19, 1999

1 Preamble, (November 1, 1999)

This is the report of the subcommittee on bioinformatics, a subcommittee of the UCD Genomics/Bioinformatics FTE Proposal. Excerpts from this report were included in the Genomics report written by Alan Bennett and submitted to the Provost in April 1999. Some proposed implementation details have changed as the genomics proposal evolved since then. In particular, the proposed bioinformatics center has become merged with the genome center, and the position of Associate Director of the Genome Center, in charge of Bioinformatics, has been created and is now being advertised (see Science Nov. 5, 1999). That position was not enumerated in this report.

Committee members of the bioinformatics subcommittee were:

• Dan Gusfield (Computer Science, Chair)

• Clark Lagarius (Molecular & Cellular Biology)

• David Rocke (Graduate School of Management)

• Grace Rosenquist (Neurobiology, Physiology & Behavior)

• George Roussas (Division of Statistics)

• Michael Syvanen (Medical School)

• John Yoder (Vegetable Crops)

2 What is Bioinformatics?

Bioinformatics and Computational Molecular Biology are generally concerned with the use of computation and large, cross-species, organized databases of biological information to augment or leverage traditional laboratory-based biology. Bioinformatics has become critical in biology due to recent changes in our ability and determination to acquire massive biological data sets (for example through genomic-level sequencing, and through expression monitoring of multiple mRNAs and even proteins), and due to the ubiquitous (almost routine) successful biological insights that have come from the comparison of the already available sequence data. Quoting from the proposal to establish a UC Life Sciences Informatics Program:

The capabilities to acquire this information have become so powerful that the volume of new data generated in some studies is growing exponentially ... There is general agreement that significant new understanding of basic biology and biomedical concerns will come from analyzing the vast amounts of data being generated. So important has this domain become that it has acquired its own name – bioinformatics.

The most mature example of the power of bioinformatics is from the accumulation, curation, and use of DNA and protein sequence data, and we will first use this example to illustrate the paradigm and potential of bioinformatics.

2.1 Sequence-oriented bioinformatics as a first paradigm

Sequence comparison, particularly when combined with the systematic collection, curation and search of databases containing biomolecular sequences, has become essential in modern molecular biology. One fact explains the importance of molecular sequence data and sequence comparison in biology.

In biomolecular sequences (DNA, RNA or amino acid sequences), high sequence similarity usually implies significant functional or structural similarity.

Evolution reuses, builds on, duplicates and modifies those structures (proteins, exons, DNA regulatory sequences, morphological features, enzymatic pathways, etc.) that have been “successful” (left as a vague concept). Life is based on a repertoire of structured and interrelated molecular building blocks that are shared and passed around. The same and related molecular structures and mechanisms show up repeatedly in the genome of a single species, and across a very wide spectrum of divergent species. “Duplication with modification” [3, 6, 4, 5] is the central paradigm of protein evolution, wherein new proteins and/or new biological functions are fashioned from earlier ones. R. Doolittle [5, 6] emphasizes this point as follows:

The vast majority of extant proteins are the result of a continuous series of genetic duplications and subsequent modifications. As a result, redundancy is a built-in characteristic of protein sequences, and we should not be surprised that so many new sequences resemble already known sequences.

and

“... all of biology is based on an enormous redundancy ...”.

The following quotes reinforce this view and suggest the utility of the “enormous redundancy” in the practice of molecular biology. The first quote is from Eric Wieschaus, co-winner of the 1995 Nobel prize in medicine for work on the genetics of Drosophila development. Describing the work done years earlier, Wieschaus says

We didn’t know it at the time, but we found out everything in life is so similar, that the same genes that work in flies are the ones that work in humans.

And fruit flies aren’t special. The following is from a book review on DNA repair [11]:

Throughout the present work we see the insights gained through our ability to look for sequence homologies by comparison of the DNA of different species. Studies on yeast are remarkable predictors of the human system!

So “redundancy”, and “similarity” are central phenomena in biology. But similarity has its limits – humans and flies do differ in some respects. These differences make conserved similarities even more significant, which in turn makes comparison and analogy very powerful tools in biology. Lesk [9] writes:

It is characteristic of biological systems that objects that we observe to have a certain form arose by evolution from related objects with similar but not identical from. They must, therefore, be robust, in that they retain the freedom to tolerate some variation. We can take advantage of this robustness in our analysis: By identifying and comparing related objects, we can distinguish variable and conserved features, and thereby determine what is crucial to structure and function.

The important “related objects” to compare include much more than sequence data, because biological universality occurs at many levels of detail. But it is usually easier to acquire and examine sequences than it is to examine fine details of genetics or cellular biochemistry or morphology. For example, there are vastly more protein sequences known (deduced from underlying DNA sequences) than there are known three-dimensional protein structures. And it isn’t just a matter of convenience that makes sequences important. Rather, the biological sequences encode and reflect the more complex common molecular structures and mechanisms that appear as features at the cellular or biochemical levels. Moreover, “nowhere in the biological world is the Darwinian notion of ’descent with modification’ more apparent than in the sequences of genes and gene products” [6]. Hence a tractable, though partly heuristic, way to search for functional or structural universality in biological systems is to search for similarity and conservation at the sequence level. The power of this approach is made clear in the following quotes from [10] and [1] respectively:

Today, the most powerful method for inferring the biological function of a gene (or the protein that it encodes) is by sequence similarity searching on protein and DNA sequence databases. With the development of rapid methods for sequence comparison, both with heuristic algorithms and powerful parallel computers, discoveries based solely on sequence homology have become routine.

Determining function for a sequence is a matter of tremendous complexity, requiring biological experiments of the highest order of creativity. Nevertheless, with only DNA sequence it is possible to execute a computer- based algorithm comparing the sequence to a database of previously characterized genes. In about 50% of the cases, such a mechanical comparison will indicate a sufficient degree of similarity to suggest a putative enzymatic or structural function that might be possessed by the unknown gene.

So large-scale sequence comparison, usually organized as database search, is a very powerful tool for biological inference in modern molecular biology. And that tool is already almost universally used by molecular biologists. The final quote reflects the potential total impact on biology of the sequence data and its exploitation in the form of sequence database searching. It is from an article [7] by Nobelist Walter Gilbert:

The new paradigm now emerging, is that all the ‘genes’ will be known (in the sense of being resident in databases available electronically), and that the starting point of biological investigation will be theoretical. An individual scientist will begin with a theoretical conjecture, only then turning to experiment to follow or test that hypothesis.

Emerging uses of sequence data

One of the most compelling reflections of the success of the bioinformatics paradigm is the diverse and often surprising ways people have found to use available sequence data - beyond the search for similarities that suggest functional similarities. As an incomplete list, this includes the comparison of available sequence data to find genes in newly sequenced data; to compare genome organization in different species; in molecular epidemiology to trace the progression of a disease; to build phylogenetic histories; to compare those phylogenies to establish symbiotic relationships between different organisms; to quickly identify different micro-organisms without culturing; to diagnose and set the prognosis of certain diseases (cancer for example); for genetic screening and to quickly detect polymorphisms without sequencing individual organisms. Most important, sequence-oriented bioinformatics and genomics, particularly the correlation of sequence data with molecular function, or structure data, or phenotypic data has established the base for functional genomics, pharacogenomics, proteomics, and proposals for a Human Phenome Project. A huge and growing commercial industry has grown from that base.

Caveat

The use of sequence similarity is extremely powerful, and its importance is growing. However, there is no one-one correspondence between sequence and structure or sequence and function, because the converse of the first fact is not true. That is, high sequence similarity usually implies significant structural or functional similarity (the first fact), but structural or functional similarity does not necessarily imply sequence similarity. On the topic of protein structure, F. Cohen [2] writes “... similar sequences yield similar structures, but quite distinct sequences can produce remarkably similar structures.” This converse issue is one indication of the many open research areas even in sequence-oriented bioinformatics.

2.2 Bioinformatics extends beyond sequence data and genomics

Although sequence-oriented bioinformatics is the most mature, and to date the most successful, subarea of bioinformatics, the same paradigm can and will be extended to other types of biological data. Among others, this includes protein structure data, protein-protein interaction data, protein-DNA interaction data, data on enzymatic and biochemical pathways, webs of neurological structures and pathways, population-scale data, large-scale gene expression data, ecological and environmental data, and even satellite data of plant growth integrated with large-scale weather and soil data. Ultimately, bioinformatics and computational biology will have the greatest impact in the area of “systems biology”, the integration of relevant biological data at many levels of observation, and the response of the system to changes in the data. Leroy Hood spoke on systems biology during his recent visit and stressed the importance and complexity of systems-level biology.

The growth of bioinformatics and computational biology is just beginning. Many pharmaceutical and bio-technology companies are developing computational molecular biology and informatics groups. Some educational programs have been developed, but there are only a few institutions that have developed a concentrated strength in bioinformatics and computational molecular biology.

The challenge to biology is to more fully exploit the available large-scale biological data and computations that one can efficiently do on that data, to make important biological discoveries. The challenge to bioinformatics and computational molecular biology is to develop efficient methods and systems to facilitate those discoveries.

In this FTE initiative, we should not narrowly concentrate on just the subareas of bioinformatics that have already proven invaluable, but over the next several years should also invest in the larger, future-oriented growth areas in bioinformatics, particularly systems biology.

3 The present situation at UCD

Although UCD has great strengths in biology generally, it has been slow to develop concentrated strength in bioinformatics, computational molecular biology and their relationship with genomics. However, this is now changing.

There is now a cadre of biologists on campus who actively incorporate the use of bioinformatics tools into their work, at the sequence level, in structure modeling, and in linking together and simulating complex neurological structures. There is a growing number of biology and chemistry graduate students and post-docs who are attempting to learn the needed technical aspects of computer programming and bioinformatics by taking classes in the computer science department; the bio-technology program organized a widely-attended multi-day workshop on bioinformatics and genomics in summer 1998; there was a widely-attended seminar series on genomics/bioinformatics in agriculture in fall 1998; a graduate course on theoretical aspects of sequence-oriented computational biology is taught every other year in the computer science department, and a book published along the lines of that course [8]; there will be three graduate courses given on the use of sequence-oriented bioinformatics tools in winter and spring 1999 (one in AES, one in DBS and one in the Medical School), and a course on the foundations of bioinformatics is being developed in computer science. There is a small group in the computer science department that studies, develops and implements sequence-oriented bioinformatics tools. That group has had eight postdoctoral students in the last several years, two who now have faculty positions and continue to focus on computational biology, one who won the DOE distinguished Human Genome Postdoc fellowship here, one who has continued with another postdoc position in a large bioinformatics group at the German Cancer institute, and one who is head of a 30 person bioinformatics unit at a biotech/genomics company; another bioinformatics Ph.d student (who actually received his degree at UC Berkeley) is now doing bioinformatics research in industry. The group also employed two UCD undergraduates who are now graduate students at Stanford focusing on bioinformatics, one in an MD/Ph.d. program, and the other in CS/MIS. Another group in computer science has been working with neurobiologists to build relational databases of brain structures, and graphical, visual tools; work is expected to continue with the submission of a major grant application. The biostatistics affinity group is moving more towards genetics and genomics, and a statistical geneticist has recently been hired in the Rowe program. There are faculty members in EVE who have developed web-accessible databases for evolutionary trees, and who incorporate the use of phylogenetic software in their courses. Evolution and Ecology and Ornamental Horticulture have also incorporated linkage analysis and QTL analysis software into some of their graduate courses. There is a computational biology group centered at ITD; superficially, their focus has very little intersection with computational molecular biology and bioinformatics, but at a deeper technical level, they face many of the same modeling and simulation issues that arise in some parts of computational molecular biology. There is an effort in medical informatics, and now an established masters program, which also has little superficial intersection with molecularly oriented and genomic-oriented bioinformatics, but again has some of the same technical problems, and the potential to fuse together with computational molecular biology and bioinformatics.

So despite the slow start of bioinformatics on campus, it is beginning, and the potential for bioinformatics and computational molecular biology is great at UCD due to the diversity and high number of biologists on campus. Davis has the additional potential of close collaboration with the genomics and bioinformatics efforts at the Human Genome Centers at the Lawrence Livermore National Lab and at the Lawrence Berkeley National Lab. Several faculty, and students on campus have had ties to those centers. There is additional potential for collaboration with local biotech companies who have an active interest in bioinformatics. Moreover, additional faculty in various areas outside of biology, such as Computer science, Engineering, Statistics and Mathematics, are eager to develop programs and positions that build on their different strengths and concentrate on different aspects of computational biology, and yet integrate and interface well with such efforts in DBS, AES, and the Medical School.

4 The need for bioinformatics research at UCD

The use of computation in biology is growing and will become more central without any explicit central effort. However, that is not enough. Despite the increased use of bioinformatics tools at UCD, what is lacking in comparison to universities with recognized strength in bioinformatics, is a core of people who actually analyze, develop and implement rather than just use bioinformatics tools and methodologies. What is needed is a core of people who do bioinformatics research, publish in bioinformatics venues, and are recognized by the bioinformatics communities. Having such people on campus will not only make bioinformatics at UCD more visible, but will facilitate and expand the effective use of bioinformatics by other biologists and students on campus.

UCD cannot move to the next level of sophistication in bioinformatics, or even in the use of bioinformatics tools, without people whose research and teaching explicitly focuses on bioinformatics as a subdiscipline in itself, in conjunction with research in traditional biological areas.

4.1 The need for a center

Because bioinformatics touches so many subareas of biology, and deeply involves researchers from outside of biology, there will be no single department that can naturally house all bioinformatics researchers. Moreover, it is essential that researchers in bioinformatics have serious interaction with biologists who are not specialists in bioinformatics but who use bioinformatics tools to address biological problems. For those reasons, there needs to be a place where the bioinformatics specialists interact among themselves, and are visible and yet are easily accessible to the rest of the campus. There needs to be a central group that organizes seminars, encourages outside visitors, helps to develop curriculum and to supervise graduate students, provides research facilities, and coordinates funding efforts. Clearly, a bioinformatics center is needed. Such a center could be aligned with the proposed genomics center.

A center for bioinformatics could play a service role on campus as well as a research role. It could collect, install and maintain essential software and databases, it can make specialized machines available to people from outside of the center, it could consult and offer advise, and it could offer courses on the use of bioinformatics tools. The need and desire for such services, and dedicated staff, is very great on campus. IT does not adequately provide such services at the level desired by the biological community on campus. It should be understood, however, that the campus would have to finance that service role, either through recharges or through support from central campus funds.

Because cross-discipline interaction, and interaction with non-specialists is so crucial to bioinformatics, hopefully, the center will be located on the main campus, rather than south of U.S. 80.

4.1.1 Details on service role of a center

First, it has to be emphasized that the infrastructure and operating costs for campus-wide service must be provided by central campus or by recharge. Moreover, the staff providing service will be separate from the research staff. The key function of the center will be research, but if given proper support from central campus, it would be natural to provide much needed services to the entire campus. The following is an outline of a possible way to structure the service.

Biocomputing Infrastructure Support for the Bioinformatics Programs: I. Charge for the UCD Biocomputing Center for Bioinformatics A. Maintain and develop computer infrastructure in bioinformatics (and

genomics)

B. Educate and assist faculty, students and staff with regular workshops, classes and consultation.

C. Forge links with academic, industrial and governmental genomic agencies.

II. UCD Biocomputing Center (associated with the campus-wide Bioinformatics Program))

This facility would house computer labs with 20-30 Workstations for classes (e.g. similar to UCD visualization lab). These labs would have the latest technology for instruction with computers. For example, all information from the instructor’s computers could appear in a window in the student’s monitor, if desired. Space on each side of the computer/workstation should be adequate for student notebooks. (These are suggestions of the Pittsburgh supercomputer staff, who give frequent workshops.)

III. Staff for the Biocomputing Center

A. Manager (Ph.D. level): 50% salary from the Center/ 0.5 FTE from a department or section in the Division of Biology. This person would manage the Support Program for the Center of Biotechnology In addition this person would maintain his/her own research program. His/her teaching load should be reduced because of the teaching load in the Bioinformatics center. Consultation with faculty, students, staff will be a part of his/her job description.

B. Associate Manager: This staff position would be funded 100% by the center. The associate director would most likely have a Ph.D and would be expected to know and keep up with programs available in the literature and on the web. Consultation on appropriate programs to use for particular problems will be a major and important part of the Assoc. director’s job. Organizing and teaching in the workshops, classes will be also expected.

C. Programmer(s): This (These) staff position(s) would be under the control of the Director.

D. Technical Support for Hardware Maintenance: At least 1 technician should be employed to maintain the workstation/computers in the Center.

III. Advisory Board An Advisory board composed of faculty members would advise the center on computer programs, workshops, and classes.

5 Relationship of bioinformatics with the Computational Biology component of the Computational Science FTE initiative

The Computational Science and Engineering FTE initiative includes the subarea of computational biology. Computational molecular biology is closely aligned with bioinformatics, although there is no definition of the two fields that is completely agreed on. Computer Science, ITD and Mathematics contributed preproposals that include some aspects of computational molecular biology, and ITD contributed a preproposal that includes other aspects of computational biology. Clearly, hiring plans in computational molecular biology should be coordinated as much as possible with hiring plans in bioinformatics. This is both to avoid redundant hiring, and to leverage the efforts of both groups.

While there is no perfect way to distinguish between the fields of computational molecular biology and bioinformatics, there is a distinction in the kinds of people who might be hired under the two initiatives. In both cases, it is essential that the people we hire be active in developing methodology, and yet closely aligned with its application in one or more specific biological subareas. However, it is natural to expect that people hired under the bioinformatics initiative might have a greater orientation to the biological applications, while the people hired under the computational science initiative might have a greater orientation to methodological issues. This reflects both the differences in the flavor of the two initiatives, and the fact that people have to be housed in specific departments and sometimes teach in areas other than their research specialty. Still, it may turn out that someone hired in bioinformatics may have their primary training outside of biology, while someone hired in computational biology may have their primary training in biology.

6 Specific FTE proposals in bioinformatics

We propose the hiring of seven faculty in bioinformatics. As detailed in section 7 below, these would likely be hired in several different departments across several different colleges. The following specific subareas of bioinformatics are listed in general (but not precise) order of hiring priority, and in order of their relationship to the general field of genomics. Also, the categories are not precise and there can be great overlap in the areas. Note that the numbers do not add to seven, allowing the flexibility to change priorities in response to hiring opportunities, to reflect the views of early and major hires, and to changes in the field.

1. Two FTE in DNA and protein sequence analysis, particularly multiple sequence comparison and clustering. Other emphases include gene finding, motif detection and characterization, and development of biologically effective and computationally efficient models and methods for sequence comparison. These areas are at the heart of present-day sequence-oriented bioinformatics, as discussed earlier.

2. One or two FTE in interspecies genomic comparisons. For example, the genome center at LLNL is working on man/mouse genome comparisons. These comparisons involve more than gene comparisons, for example genome organization and synteny.

3. One or two FTE in protein structure modeling, and the inference of structural features from sequence. This also includes methods such as homology modeling and threading.

4. One FTE in the design, use and integration of databases for biological data. With the number of databases growing exponentially, it is essential that they be made to work together. Moreover, as the complexity of the biological data increases (for example as we move into systems biology) the complexity of the databases will increase as well.

5. One or two FTE in visualization, modeling, simulation and analysis of complex biological systems, for example biochemical pathways, brain structures. Complex databases are being constructed for these systems. What is needed are algorithms and insight into how to exploit these databases to both help the researcher handle the dataload, and to find interesting features in the data.

6. One FTE in computational problems in genomic laboratory protocols, for example the design and use of array technology, pooling methods in DNA sequencing, or sequencing by hybridization. There are many algorithmic, mathematical and statistical problems here.

7. One FTE position in computational or statistical issues in phylogenetics.

8. One FTE position molecular quantitative genetics, for example, QTL mapping.

7 Search and Hiring Logistics

Bioinformatics spans many of the established biology, math, statistics and engineering disciplines, and the background and present research focus of a person in bioinformatics can be very diverse. For example, an individual might focus on protein structure, or genetics, or evolution, or epidemiology, or sequence analysis, or statistics or computer science etc. It would therefore be difficult to pre-allocate FTE positions to specific departments or divisions. The committee has not come to a consensus on the best way to proceed here. There were two differing proposals.

In one proposal, the administration could earmark a specific number of FTE positions for bioinformatics, but not allocate these to specific colleges or departments. Instead, it (through the bioinformatics committee) would specify a list of research areas in bioinformatics that we are interested in seeing develop at UCD, and give a general ’hunting license’ to many departments to search for candidates in those areas. A standing bioinformatics committee would be involved in any resulting interviews. That committee, along with the involved department, would then make any recommendation to the administration to hire that particular person in one specific department.

The proposed scheme not only allows for wider participation of different units on campus, and more cohesive hiring, but it allows the new hires to have a larger voice in any subsequent hires, and builds in the flexibility to change emphases as the field develops and circumstances change. However, the scheme is not without problems. For example, different areas interview at different times of the year making it difficult to compare candidates in different fields. Moreover, there was opinions that the scheme was impractical and that departments would not have sufficient incentive to actually search for candidates.

The alternative proposal was for a bioinformatics center, or some new entity or program, to hold the FTE positions, be responsible for search and hire, in loose coordination with established departments. More formally, a division of bioinformatics, similar in structure to the division of statistics, could be established for this purpose. If such a division were established, it was expected that people in it would hold joint appointments with other departments.

8 Curriculum Development

8.1 proficiency in use vs. development

There is a clear need to introduce the use of bioinformatics tools at the undergraduate level. In the case of sequence-oriented bioinformatics, this should be done after the students have studied sufficient genetics and molecular biology to understand the biological questions that the tools allow one to address. In the case of structure-oriented bioinformatics, the students must study sufficient biochemistry, particularly a course on protein structure. It may be possible to introduce the use of these tools into established courses, or it may be necessary to develop additional courses that focus entirely on bioinformatics tools.

In addition to courses or lab modules that teach the use of tools, some students will want a deeper understanding of the way bioinformatics tools address biological questions. For that, there is a need for an undergraduate course that focuses on the fundamental biological, mathematical and algorithmic chain of reasoning leading to the models that lie behind these tools. Such a course requires more sophistication in mathematics, and some intuitive understanding of can be accomplished by computer programming, but does not require extensive exposure to programming. Such a course is currently being developed in the computer science department.

It is also desirable to have some students, both biology and non-biology majors (particularly engineering majors), develop the deep programming and computer skills to modify, develop and implement new bioinformatics tools. It may be possible to reserve some space in undergraduate programming and database courses for biology students, and some space in laboratory biology courses for some computer science students. We should also give some thought to a hybrid major between biology and computer science (or possibly in bioengineering, depending on the direction that new department takes) to serve the appropriate students.

Also, see the Altman Proposal for a bioinformatics curriculum in Bioinformatics, Vol. 14, no 7 1998 pages 549-550.

8.2 Specific Curriculum proposals

We should develop additional undergraduate and graduate courses in bioinformatics and genomics. The course syllabus below is only one of several possible courses. It is for an undergraduate course to be taught first in spring 2000.

ECS 124 THEORY AND PRACTICE OF BIOINFORMATICS (4) III Lecture: 3 hours Laboratory: 1 hour

Prerequisites: Course CSE 10 or 30 or E 5 or E 6; Stat 12 or 13 or 32 or 100 or Math 131/Stat 131A; Bio Sci 1A or 101 or MCB 10

Grading: Letter; 5-7 homework/laboratory sets (60

Catalog Description:

Fundamental biological, mathematical and algorithmic models underlying bioinformatics; sequence analysis, database search, gene prediction, molecular structure comparison and prediction, phylogenetic trees, high throughput biology, massive datasets; applications in molecular biology and genetics; use and extension of common bioinformatics tools.

Goals:

I. Understanding the role and utility of bioinformatics in modern biology II. Understanding basic biological, mathematical and algorithmic con-

cepts, techniques and models underlying bioinformatics tools III. Mastery of common bioinformatics tools IV. Simple programming in Perl or Java to extend the utility of common

bioinformatics tools Expanded Course Description: I. Initial examples of the power of bioinformatics in modern biology A.

The importance of sequence and structure comparison and of database search B. The use of sequence analysis in laboratory protocols C. The use of phylogenetics in evolution and non-evolutionary areas of biology

II. Sequence analysis A. Probabilistic and biological models underlying sequence alignment B. Computational efficiency and the need for compromises in the models C. The general technique of Dynamic Programming D. Pairwise sequence alignment - algorithms for global, local alignment and variations E. Algorithms for multiple sequence alignment and the identification/use of motifs F. Database search - FASTA, BLAST, PSI-BLAST, scoring matrices, statistical significance and its significance G. Creation and use of motif models H. Novel uses of sequence analysis in studying DNA, RNA and proteins I. Sequence analysis in genomics and high throughput biology

III. Phylogenetic algorithms A. Probabilistic and ideal-data models underlying phylogenetic algorithms B. Distance-based methods C. Character/parsimonybased methods D. Maximum-likelihood methods E. PAUP, PHYLIP F. Evolutionary and non-evolutionary uses for phylogenetics G. The interaction of phylogenetics and sequence analysis

IV. Protein and RNA structure comparison and prediction A. Ideal-data models underlying structure comparison and prediction B. Algorithms for RNA folding C. Methods and problems in protein structure comparison and prediction D. Biological use of structure prediction and comparison tools

V. Overview of common bioinformatics utilities and web-based resources such as GCG and Entrez

Textbooks: Required Text R. Durbin et al., Biological Sequence Analysis: Probabilistic Models of

Proteins and Nucleic Acids, Cambridge Press, 1998

A. Baxevanis and B. Ouellette, Bioinformatics: A Practical Guide to the Analysis of Genes and Proteins, Wiley-Interscience 1998

Supplemental Text M. Bishop and C. Rawlings, DNA and Protein Sequence Analysis: A

practical Approach, IRL Press, 1997

D. Gusfield: Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology, Cambridge Press, 1997.

Supplemental readings and notes distributed in class Homework: Each homework set includes creative problems as well as recitation prob-

lems to strengthen understanding and discover new material.

Computer Usage: The lab portion of the class will emphasize practical computer exercises

using both established bioformatics software and writing simple programs in Perl or Java.

ABET Category Content: Engineering Science: 1 unit Engineering Design: 0 unit Instructor: Dan Gusfield Prepared by: Dan Gusfield (April 1999) The course is aimed both at biology and computer science students. It

is expected that the typical biology student will have a stronger background in molecular biology, genetics and biochemistry (not listed as a prerequisite) than is reflected in the prerequisite list, and that the computer science student will have a stronger background in programming and mathematics than is listed in the prerequisites. Some of the laboratory assignments will be done by groups mixing biology and computer science students whose backgrounds should complement each other.

The laboratory portions of the course will teach the hands-on computer tools, while the lectures will focus on the fundamental biological, mathematical and algorithmic chain of reasoning leading to the models that underlie these tools. Thus, the course requires some sophistication in mathematics, and some intuitive understanding of what can be accomplished by computer programming, but does not require an extensive background in programming.

9 Appendix: Details of a similar effort at Iowa State

9.1 Overview from Dan Voytas at ISU

ISU began developing bioinformatics over the past 2 years. It started with the formation of the Iowa Computational Biology Lab – a group of faculty from a variety of depts who began meeting once a week in a seminar, journal club format. Things really gained a footing with the addition of three new hires last year (including Volker Brendel from Stanford). We have an ongoing search for an additional bioinformaticist this year.

To coordinate genomics and bioinformatics efforts, a group of faculty (at the administration’s request) formed the Iowa Genome Frontiers Lab. Briefly, it is an integrated set of research facilities, including microarray, high throughput sequencing, proteomics, robotics and comp. bio components. The administration has kicked in about $600K so far, and we anticipate another 400K over the coming year (some of this is detailed in the budget).

Specifically in the area of comp.bio, the University has funded renovation of space for a comp. lab (65K), and they contributed toward a 16-node parallel computing system that Volker is developing ( 100K, I believe). They have also made substantial contributions as matching funds to various proposals. For example, we have a training grant into NSF for which they’ve provided $200K over 5 yrs for equipment as well as salary money for a systems analyst.

9.2 Additional Details from Jim Cornette at ISU

One of the hard things I have worked on this Fall is trying to get an understanding of the computer needs of our community. I am of the opinion that there should be a system freely available to all on campus that has the characteristics shown at the end of this note. It is easier to provide centrally for computational genomics than for computational molecular structure. Designing the hardware is very difficult in either case. We have (one of our faculty, Alan Myers, has) a DEC that runs GCG as a central machine available upon request from a faculty member. We proposed to move that to the computation center and have it centrally maintained and expand it to two networked remote-server computers and have SeqWeb interface (a web interface restricted to campus but accessible from computers on campus that can open a unix window). You can get a lot of information from the GCG web site. Then, we proposed getting a couple of SGI’s with Molecular Simulations, Inc software for computational chemistry. These would be available to all – several labs have computational chemistry machines available only to their labs.

Central to our proposal was (1) maintenance of hardware by the Computation Center, and two postdocs half-time assigned to maintain and teach how to use software. We decided on postdocs because we would have a lot of difficulty attracting and retaining regular employees in this area.

We have applied for an IGERT grant that Dan V will tell you about, and it is designed for RA support (four new students/year for the next five years – I think the university has some obligation to continue some of those beyond the five years), and 5K/student that can be used by the student to buy his or her own PC (or notebook).

We also have RA support from Pioneer Hi-Bred, International (a seed company) of 100K/year for the next five years, designed to support five students per year (17K salary plus 3K benefits, travel, supplies) and may get support from a software companies SBIR grant to NIH for three students per year for two years. We are not seeing very much RA from the university. There has been a suggestion of perhaps four per year to a rather broad informatics category for which we could compete.

I have no feel for space required. Probably an office and a computer lab will do it. On the other hand, some of our students are, and will be, doing some wet lab work, and I am out of that loop.

Among the computational tasks that might be expected of a universitywide computation system for molecular biology are:

1. Data base search. Search any of several data bases for a known sequence, search the headers for all proteins of a certain classification,

Data bases to be held locally:

A. Genbank B. dbEST, dbSTS C. PDB, NDB D. Swiss Protein E. Signaling pathway database. F. Any of several genomes, including cattle, chicken, pig, Human, Drosophila, Arabidopsis, Maize, Soybean, Rice, ...

2. Homology detection, sequence similarities.

3. Homology detection, 3D similarities.

4. Contig assembly.

5. Identify open reading frames, exons, and introns.

6. Construct phylogenetic trees.

7. Predict RNA secondary structure.

8. Predict protein secondary structure.

9. Alignment of two sequences (DNA or protein).

10. Alignment of multiple sequences (DNA or protein).

11. Dot plot of two sequences.

12. Molecular visualization and computational chemistry. A. Both static and dynamic molecular structural computations using

CHARMm or AMBER or an equivalent system.

B. Display protein tertiary structure (ball and stick, ribbon, etc.). C. Display RNA secondary structure. D. Display DNA/RNA tertiary structure (see http://synapse.lanl.gov) E. Graphical display of orf, exon, intron location.

13. Deposit data in data banks.

14. Determination of common motifs.

15. Search for known motifs (promoter, splice site, antigenic peptide, etc.)

16. Primer design.

17. Nucleotide to protein translation.

18. Statistical analysis (a bit of a broad category).

19. A Web server for: Maize genome, Soybean genome, Swine genome

9.3 Additional software capabilities needed

In addition to the above list, additional software capabilities have been suggested along the lines of software available at the Pittsburgh Supercomputing Center.

Among the computational tasks that might be expected of a universitywide computation system for molecular biology are:

1. Data base search. Search any of several data bases for a known sequence, search the headers for all proteins of a certain classification,

Data bases to be held locally: A. Genbank B. dbEST, dbSTS C. PDB, NDB D. Swiss Protein ALSO PIR (much larger (more sequences) than swiss protein) E. Signaling pathway database. F. Any of several genomes, including cattle, chicken, pig, Human, Drosophila, Arabidopsis, Maize, Soybean, Rice, ...

2. Homology detection, sequence similarities. PSC has NWGap, MaxSegs, FShift (FrameShift), FASTA Use BLAST server when appropriate

3. Homology detection, 3D similarities. PSC has Profiless (3d profiles), 1dto3d (aligns sequence to structure)

4. Contig assembly. Whatever is in GCG

5. Identify open reading frames, exons, and introns. Whatever is in GCG - this is probably better done using web resources specialized to genes in specific classes of organisms - maybe set one up for plant genes at Davis.

6. Construct phylogenetic trees. Phylip, PAUP in GCG

7. Predict RNA secondary structure. MFold in GCG, Jake Maizel’s RanFold, trying to get Bruce Shapiro’s Genetic Algorithm for RNA folding

8. Predict protein secondary structure. Whatever is in GCG - again specialized servers on the web are probably better and should be used

9. Alignment of two sequences (DNA or protein). NWGap, MaxSegs, FShift

10. Alignment of multiple sequences (DNA or protein). MSA (need large memory machine to be worthwhile), CLustalW, SAGA, Hummer package

11. Dot plot of two sequences. GCG

12. Molecular visualization and computational chemistry. A. Both static and dynamic molecular structural computations using

CHARMm or AMBER or an equivalent system.

B. Display protein tertiary structure (ball and stick, ribbon, etc.). Graphx, MolMol, RasMol (both the original and Berkley version)

C. Display RNA secondary structure. GCG D. Display DNA/RNA tertiary structure (see http://synapse.lanl.gov)

Graphx E. Graphical display of orf, exon, intron location. GCG programs

13. Deposit data in data banks.

14. Determination of common motifs. MEME, Consensus

15. Search for known motifs (promoter, splice site, antigenic peptide, etc.) searchprosite, searchblocks, mast, profiless, hmmPfam, GCG Motifs program

16. Primer design. GCG

17. Nucleotide to protein translation. GCG

18. Statistical analysis (a bit of a broad category).

19. A Web server for: Maize genome, Soybean genome, Swine genome Also, the support staff should be able to advise and help in the informatics

needs of small genome programs, such as the database and web needs that arise in UCD project to do expression monitoring in the cotton genome.

References

[1] C. Caskey, R. Eisenberg, E. Lander, and J. Straus. Hugo statement on patenting of DNA. Genome Digest, 2:6–9, 1995.

[2] F. E. Cohen. Folding the sheets: Using computational methods to predict the structure of proteins. In E. Lander and M. S. Waterman, editors, Calculating the Secrets of Life, pages 236–271. National Academy Press, 1995.

[3] R. F. Doolittle. Of Urfs and Orfs: A primer on how to analyze derived amino acid sequences. University Science Books, Mill Valley, CA., 1986.

[4] R. F. Doolittle. Redundancies in protein sequences. In G. Fasman, editor, Prediction of protein structure and the principles of protein conformation, pages 599–624. Plenum, 1989.

[5] R. F. Doolittle. Searching through sequence databases. In R. F. Doolittle, editor, Methods in Enzymology vol. 183. Molecular Evolution: Computer Analysis of Protein and Nucleic Acid Sequences, pages 99–110. Academic Press, 1990.

[6] R. F. Doolittle. What we have learned and will learn from sequence databases. In G. Bell and T. Marr, editors, Computers and DNA, pages 21–31. Addison-Wesley, 1990.

[7] W. Gilbert. Towards a paradigm shift in biology. Nature, 349:99–99, 1991.

[8] D. Gusfield. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. Cambridge University Press, 1997.

[9] A.M. Lesk. Computational molecular biology. In A. Kent and J.G. Williams, editors, Encyclopedia of Computer Science and Technology, Vol. 31, pages 101–165. Marcel Dekker, 1994.

[10] William R. Pearson. Protein sequence comparison and protein evolution. Tutorial T6 of Intelligent Systems in Mol. Bio., Cambridge England, July 1995.

[11] B. S. Strauss. Book review: DNA repair and mutagenesis. Science, 270:1511–1513, 1995.