Primary Contact:

Large-Scale Data Mining; Pilot Project in Human Genome

Krzysztof Fidelis
Structural Biology
Lawrence Livermore National Lab
fidelis1@llnl.gov

Tom Slezak
Biology and Biotechnology Research Program
Lawrence Livermore National Lab
slezak@llnl.gov

INTRODUCTION

We are at a point in time where science, business, and government must face many common technical challenges in their struggle to keep moving forward. The challenges stem from our growing abilities to create and collect complex data at tremendous rates, followed naturally by our need to manage and analyze that same data. To maximize the value of this data, we first must be able to access and manipulate it as structured, coherent, integrated information. Scientific data management, the discipline of improving the scientist's interactions with data, addresses this need in the scientific arena (the domain of this pilot project). Data mining and knowledge discovery is a cornerstone of scientific data management, and of advanced management of data from all sectors in general. Data mining has the narrower focus of helping automate the exploration and characterization of the data being generated. This leaves the analyst/scientist free to concentrate on the actual interpretation and use of the data.

This white paper briefly describes a new, aggressive effort in large-scale data mining at Lawrence Livermore National Labs (LLNL). The implications of "large-scale" will be clarified in the Barriers Section. In the short term, this effort will focus on several mission-critical questions in the Human Genome project. We will adapt current data mining techniques to the genome domain, extend them to quantify the accuracy of inference results, and lay the groundwork for a more extensive R&D effort in large-scale data mining. A major aspect of the approach is that we will be leveraging a fully-staffed data warehousing effort in the human genome area. The long term goal is to build a strong applications-oriented research program in large-scale data mining. The tools, experience and skill set gained will be directly applicable to a wide spectrum of tasks involving advanced analytics for large spatial and multidimensional data. This includes applications in ensuring Global Security (non-proliferation, stockpile stewardship), enabling Global Ecology (Materials Database for Industrial Ecology), advancing the Biosciences (Human Genome Project), and supporting work for others (Battlefield Management, Health Care).

BARRIERS

There are many challenges on the path to effective large-scale data mining. The issues are broad, and their solutions require expertise from several domains in computer science, mathematics and statistics. We introduce them by laying out several axes along which current technology must be scaled to match the demands of a data-intensive domain:

• Large datasets - Astrophysics currently has terabytes of data available for processing; earth science data will soon be measured in the petabytes. One must deal with data storage, and data transport across networks and through the storage hierarchy from tertiary storage to disk to main memory.
  
• Highly complex data - Data mining algorithms typically handle "simple" data consisting of rows of feature vectors. Native data models (before being transformed into feature vectors) are often highly structured 2D or 3D objects with complex, inter-related components. Mapping from native data into feature vectors can explode the number of features of each object, and potentially lose information in the process.
  
• High algorithmic complexity - Algorithms in this field vary dramatically. Simple naive Bayes, a fast but limited predictor, can be linear in the number of features + training examples. Decision trees, which are excellent classification tools, can range from O(nlogn) to O(n^2) or worse depending on the type of pruning done. Model induction algorithms (e.g. belief networks) with built-in assumptions that reduce complexity start at O(n^4 D^2) where n is the number of variables, and D is the average domain size for the variables. More complex algorithms are exponential.
  
• Oppressive data management demands - There are significant difficulties in mining "living data", or data that is used on a daily basis. This includes (1) different repositories hold critical pieces of information, (2) non-standard nomenclatures, (3) radically different data types and models, (4) data may be duplicative and erroneous, and (5) the models for representing data content may change at a high rate.
  
• Qualification of results - This last issue is important, but rarely mentioned. Data mining tools are decision making aids. As such, if the tool is poorly understood, then expensive and incorrect decisions could easily be made based on the output (e.g. treatment decisions in the medical world). Data mining tools generate models that have built in biases, and are often the product of heuristic, non-exhaustive searches through a problem space. Unfortunately the quality of these models (or inferences) are rarely measured, leaving the user to rely on intuition as to how far to trust the results. If these methods are to be trusted tools of any profession where the (real and opportunity) cost of a mistake is high, then the qualification of the inference results must be addressed.
  

APPROACH

There are four main strategies for overcoming the barriers facing large-scale data mining. Each addresses a different aspect of scalability.

1. Design environments and tools that support the entire data mining process from data collection, data integration and cleaning, data selection, to visualization of results.

2. Build scalable I/O architectures and interfaces. For example, build intelligent interfaces between DBMS systems and tertiary storage.

3. Develop algorithms that work with non-traditional data types such as time sequences, protein sequences, or 3D structures.

4. Scale algorithms to work with larger data sets. This involves reducing algorithm complexity, effective parallelization, and controlled sampling or filtering.

The first approach is geared towards moving data mining technologies to large scale real world applications; the data warehousing project described in the Application Domain Section below addresses the challenges raised there. The second and third approaches are important as well, and we plan to leverage results in from these areas at some point in the future. In particular, there are several major efforts at LLNL that focus on scalable I/O architectures and interfaces, including the High Performance Storage System (HPSS), the Message Passing Interface, and the Scalable I/O Facility. Other work revolving around scalable interfaces includes the Interface Data Repository, and the Conquest/OASIS projects [2, 9]. However, in our judgment the highest payoff research area for genome, and for large-scale data mining in general is the fourth approach, scaling algorithms to work with large data. The key enablers will come from a focus on parallel codes, and controlled sampling techniques.

For the pilot, we will adapt existing parallel codes like SPRINT [8] and MLC++ [3] to the human genome domain. Where advantageous we will extend other algorithms with the more obvious parallel optimizations such as numerical and graph-search parallel techniques. Our primary focus, however, will be to build a controlled random sampling framework based on the expected utility of additional sampling.

The key concept behind random sampling is the realization that, often, the economically rational decision is to use a small portion of the available data to answer a question. For interactive data mining tasks, a user might want only a rough idea of the predicted value of a variable, and so would want to cut off search when the expected accuracy reaches, say, +/-10%. Or similarly, stop when it is 95% certain that the current answer will not change no matter how much of the remaining data is seen. The methods that can support these abilities can also be used to answer questions like: "What sample size will probably be large enough to produce inferences within a given expected error," and "What is the estimated accuracy of this prediction given the data that was used to produce it."

The theoretical basis for these techniques stems from the idea that the utility of additional sampling is a measure of the expected marginal gain in inference quality [4, 5]. Determining marginal gain is a difficult problem, both from the aspect of creating an accurate mathematical model of the learning algorithm at hand, and tying the model to the sampling decision process. Initial results for decision trees can be found in Musick et. al. [4] (http://www.llnl.gov/CASC/people/musick/papers/dt.ps). The research is strongly related to ideas from learning from sparse data [6], sampling theory [1], game theory [7], and anytime algorithms [10].

There are two clear benefits of providing a controlled sampling framework. First, this research will work a critical shortcoming in many state of the art mining algorithms: the lack of a well-grounded metric by which to judge the quality of inference results. The marginal gain in inference quality is the key to providing this metric. The second major benefit is that we can control the large-scale aspect by taking samples of the data large enough to return high quality answers, but much smaller than the full-blown corpus of data.

APPLICATION DOMAIN

The technical insights from this pilot project should be readily transferrable to nearly any application of data mining to large data in the scientific, business or government arenas. Our particular focus for the short term is on applying these ideas to domain-specific questions from the human genome project. We also believe that data mining will become a central technology in data warehousing and intelligent integration techniques, aiding in schema and row identity analysis. We are pursuing that direction as well.

The genetics domain is stimulating and challenging, and the staff in that area in LLNL is interested and already contributing to a highly leveragable R&D project: "Data Warehousing and Integration for Scientific Data Management". The warehousing project marks a significant push to collect, organize and integrate the corpus of genetic map data, sequence data, protein structure, taxonomy, and other information that exists at LLNL and other sites around the world. The data infrastructure is currently under construction, and should be in place by FY98. The warehousing effort addresses "Oppressive Data Management Demands" described in the Barriers Section, and will establish an excellent testbed environment for the data mining effort.

The total data collected so far in the genome effort is not as large as in other domains (on the order of tens to hundreds of gigabytes). However, the data is growing rapidly, it is extremely complex in nature, and misinterpretation of analysis results in this domain could lead to expensive errors in deciding, for example, which gene to sequence next. The domain is a natural fit for large-scale data mining. Data mining is a vital enabling technology in this area that will help address several important research questions in the human genome effort. Furthermore, the ability to characterize the quality of the data mining results will be critical to the general acceptance of the techniques. Some examples of where these techniques are needed:

• Characterize tumor suppressing genes, and apply that model to all the genes in chromosome 19 to see if there are others that match. Note that this process can be repeated for any particular cluster of genes and chromosomes in any organism in which the scientist is interested.
• Discover new methods to find and compare protein homologs by incorporating knowledge from many non-traditional sources into the classification and modeling techniques. For example, take protein from any species where the sequence may or may not be known. Digest the protein, and develop a mass spectrometry footprint of it. Compare with other footprints. Include functional information when available, and attempt to link the unknown protein to a particular sequence in the genome.
  

DEPLOYMENT

The first usable prototype of the warehouse will be deployed by the end of FY97, and will provide the testbed for the data mining research. From the research standpoint, we will be productive within a few months of project initiation. We expect that with two scientists committed to the pilot project, strong practical results will be achievable within half a year of the start date. Based on research results achieved by one of the PI's in this area [4, 5, 6], we believe the chance of success to be high.

LEVERAGE

There are significant resources that this effort will be able to leverage. The largest impact will come from the data warehousing R&D effort between the Center for Applied Scientific Computing (CASC) and the Biology and Biotechnology Research Program (BBRP), as discussed above. Other resources include: