U.S. Department of Energy

Human Genome 1993 Program Report: Informatics

Projects to sequence several large genomes, particularly the humangenome, make the automation of nucleic acid sequencing one ofthe most important problems of biochemistry and molecular biology.Recently several groups in Great Britain, Yugoslavia, Russia, andthe United States suggested a new, easily automatable method forDNA sequencing by hybridization (SBH) with oligonucleotides,compiling the complete list of oligonucleotides of a fixed length(k-tuples) that occur in a DNA fragment (fragment vocabulary) andsubsequently reconstructing the fragment sequence by linkingmaximally overlapping k-tuples from the vocabulary.

In its current form SBH does not accomplish complete automationof genome sequencing, since the need still exists for random cloningof millions of fragments. To overcome this problem, A. B. Chetverin and F. R. Kramer recently suggesteda method for direct sequencing of large (including diploid) genomeson oligonucleotide arrays.

Unlike existing strategies for total genome sequencing, thesuggested approach would not require preliminary fragment cloningand chromosome mapping and could be completely automated.Substantial reductions in time and cost would result; preliminaryestimates show that the cost of human genome sequencing could bereduced 10- to 100-fold. Furthermore, total sequencing of anindividual diploid genome can be considered with this method, asopposed to sequencing a haploid set of fragments arbitrarilycompiled from different individual genomes. One of the stages (i.e.,fragment sorting and pool reconstruction, see below) can be usedfor direct sequencing of the total pool of cellular RNA, withobvious advantages for genetics, developmental studies, andmedicine.

In this project we plan to develop, implement, and test computeralgorithms to solve the problem of reconstructing fragmentsequences in a pool. This is important for the following reasons.First, computer processing of biochemical data is an integral andessential part of the method. Second, practical implementation ofthe method should be preceded by intensive computer modelingand theoretical analysis to determine such optimal biochemicalparameters as oligonucleotide size, mean and maximal values offragment length and pool size measured as their combined length, and signal-to-noise (s/n) ratio in hybridization procedures. Such apreliminary analysis would substantially increase reliability anddecrease the cost of collecting biochemical data. Finally, somearising mathematical problems are novel, and they haveindependent value for discrete mathematics and computerscience.

Accurate Restoration of DNA Sequences

This project will develop statistical methods and algorithms todetect potential errors in DNA sequence data and computesummary measures of sequence quality. Methods will be based on astochastic model of sequencing errors that will apply to anytechnology that generates overlapping linear sequence fragments,including gel and capillary electrophoresis. New high-speedsequencing technologies are expected to be developed that mayproduce errors in raw fragment sequences at a much higher ratethen existing methods. The problem of assembling overlappingsequence fragments will also be addressed.

Our long-term goal is to develop an efficient and fully automatedquality-control procedure that should be an integral part of anylarge-scale sequencing project. This automated procedure shouldeventually replace much expensive human effort expended inrechecking raw sequence data. Model-based statistical methods canhelp improve the efficiency of existing sequencing technology (forexample, by allowing for longer gel runs) and will be an essentialcomponent of any system that can produce high-quality finishedsequence at the target rate of 1 Mb/d.

Computer-Aided Genome Map Assembly with SIGMA(System for Integrated Genome Map Assembly)

SIGMA (System for Integrated Genome Map Assembly), a recentlyreleased graphical genome map editor, supports the following:

• graphical, mouse-based genome map editing;

• integration of data from many different types of physical andlinkage experiments and at all appropriate resolution levels, frombanded ideograms to restriction fragments;

• creation of multiple "views" on a single map;

• creation by users of new classes of map objects on demand;and

• workgroup map building through the use of client-server databasemanagement system technology.

• keeps underlying data as part of the map, allowing users to knowthe real support for any given map;

• automatically evaluates the map against underlying data, pointingout places where the two disagree; and

• creates a platform for automatic map assembly algorithms beingdeveloped by many groups worldwide.

The software, documentation, and a number of sample maps inSIGMA format, including current Genome Data Base maps, areavailable by anonymous FTP from atlas.lanl.gov.Additional information may be obtained by sending a messagecontaining only the word sigma-info tobioserve@t10.lanl.gov.

Informatics for the Sequencing by HybridizationProject

Methods for the design and analysis of massive hybridizationexperiments have been developed on a solid theoretical basis.Algorithmic information theory and minimal length encoding arebeing used to design methods for comparing partial sequence dataand databases of sequenced DNA. Preliminary experiments led tothe first identification of 55 gamma-actin cDNA clones basedon their hybridizations to 110 heptamer probes. In addition,clustering methods are being developed and applied to discovergroups of similar clones in cDNA and genomic libraries throughcomparison of their hybridization signatures. Clone clusteringrevealed transcriptional structure in human brain cDNA libraries. Apreliminary experiment demonstrated the potential of the clusteringmethod to reduce by 10 times the sequencing effort needed tocover a 12-kb segment of human genomic DNA. Mutualinformation and other concepts from information theory are beingapplied to interpret measurements optimally and approach design ofmassive hybridization experiments.

A relational database that contains a complete record of massivehybridization experiments has been developed using Sybaseclient-server technology. A complete suite of programs forexperiment design, entry of experimental data, and data analysis hasbeen built into the UNIX C-shell in order to facilitate the writingof C-shell scripts for these functions. The programs are written inC++ and interfaced with the database by using Sybase db-library.A new level of experiment design and debugging is being developedto facilitate a complete experiment design in the computer; thisdesign will then be automatically converted into robotic instructionsfor such routine laboratory operations as microtiter platemanipulation and dot-blot filter printing. Preliminary research isbeing performed using the Quintus Prolog system to interface thedatabase of hybridization experiments with databases of annotatedDNA sequences. The logic programming level will enable the rapiddesign of computational experiments as well as a uniform datarepresentation level, both of which are necessary for machinediscovery of biologically relevant patterns.

Sequencing by Hybridization Algorithms andComputational Tools

Sequencing by hybridization (SBH) requires sophisticatedcomputational procedures for data acquisition and evaluation andfor DNA screening, mapping, and sequencing applications. We havebeen developing algorithms and programs and performingsimulations to prove many SBH possibilities other than the straightsequencing of short DNA fragments. For example, we demonstrateda 10- to 50-fold increase of SBH efficiency by using overlapped andsimilar sequences in the assembly process. Furthermore, we showedthat partial sequences obtained by 100 to 1000 probes aresufficient for gene identification and recognition of overlapped andsimilar sequences.

Recently we have started to produce large sets of real hybridizationdata that define practical requirements and serve as a final checkfor the necessary programs. Several computational tools have beendeveloped to enable use of the data. The programs are based onheuristic rules and resemble expert systems resistant to commonexperimental imprecision. All the programs use hybridizationintensities without conversion to 0/1 (binary) form.

Acquisition of hybridization data from filters containing 31,000 dots(1 dot/mm2) is the first step. An image-analysisprogram (DOTS) has been developed (J. Jarvis and R. Drmanac)that automatically defines filter position and reports hybridizationintensity for each dot. Programs for evaluating and normalizing data(SCORES), identifying groups of similar clones (CLUSTERS), andordering clones (CORD) are in the final phase of development.The programs are written in C for UNIX platforms with anX-Windows interface. Through SCORES and CLUSTERS, 20,000cDNA clones have been sorted into 13,000 groups. Further, analgorithm has been developed for matching hybridization signatureswith known sequences by simulating the expected probe scores forknown sequences. The CORD program defines contigs of 1- to2-kb clones hybridized by 200 probes and provides sequence-readymaps. The maps allow clone selection for complete sequencing byless then 2 reads/bp. In various simulation experiments, CORD hasshown a tolerance to more hybridization errors than observed inour experiments and to the high abundance of Alu repeats found inhuman sequences.

Key programs remain to be developed for assembling sequence by(1) combining single-pass gel sequences having as much as a20% error rate with hybridization data from 3000 probes and (2) integrating hybridization data from similar sequences. Aprogram is also needed for using partial sequence data to identifygenes and other genome elements.

*Computer Analysis of Functional Regions of theHuman Genome