RESULTS: We have developed LeTICE (Learning Transcriptional networks from the Integration of ChIP-chip and Expression data), an algorithm for learning a transcriptional network from ChIP-chip and expression data. The network is specified by a binary matrix of transcription factor (TF)-gene interactions partitioning genes into modules and a background of genes that are not involved in the transcriptional regulation. We define a likelihood of a network, and then search for the network optimizing the likelihood. We applied LeTICE to the location and expression data from yeast cells grown in rich media to learn the transcriptional network specific to the yeast cell cycle. It found 12 condition-specific TFs and 15 modules each of which is highly represented with functions related to particular phases of cell-cycle regulation. AVAILABILITY: Our algorithm is available at http://linus.nci.nih.gov/Data/YounA/LeTICE.zip

The goal of clustering is to identify distinct groups in a dataset. The basic idea of model-based clustering is to approximate the data density by a mixture model, typically a mixture of Gaussians, and to estimate the parameters of the component densities, the mixing fractions, and the number of components from the data. The number of distinct groups in the data is then taken to be the number of mixture components, and the observations are partitioned into clusters (estimates of the groups) using Bayes ’ rule. If the groups are well separated and look Gaussian, then the resulting clusters will indeed tend to be “distinct ” in the most common sense of the word- contiguous, densely populated areas of feature space, separated by contiguous, relatively empty regions. If the groups are not Gaussian, however, this correspondence may break down; an isolated group with a non-elliptical distribution, for example, may be modeled by not one, but several mixture components, and the corresponding clusters will no longer be well separated. We present methods for assessing the degree of separation between the components of a mixture model and between the corresponding clusters. We also propose an algorithm for pruning the cluster tree generated by hierarchical model-based clustering. The algorithm starts with the tree corresponding to the mixture model chosen by the Bayesian Information Criterion. It then progressively merges clusters that do not appear to correspond to different modes of the data density.

The goal of clustering is to identify distinct groups in a dataset. Compared to non-parametric clustering methods like complete linkage, hierarchical model-based clustering has the advantage of offering a way to estimate the number of groups present in the data. However, its computational cost is quadratic in the number of items to be clustered, and it is therefore not applicable to large problems. We review an idea called Fractionation, originally conceived by Cutting, Karger, Pedersen and Tukey for non-parametric hierarchical clustering of large datasets, and describe an adaptation of Fractionation to model-based clustering. A further extension, called Refractionation, leads to a procedure that can be successful even in the difficult situation where there are large numbers of small groups.

A surface light field is a function that assigns a color to each ray originating on a surface. Surface light fields are well suited to constructing virtual images of shiny objects under complex lighting conditions. This paper presents a framework for construction, compression, interactive rendering, and rudimentary editing of surface light fields of real objects. Generalization of vector quantization and principal component analysis are used to construct a compressed representation of an object's surface light field from photographs and range scans. A new rendering algorithm achieves interactive rendering of images from the compressed representation, incorporating view-dependent geometric level-of-detail control. The surface light field representation can also be directly edited to yield plausible surface light fields for small changes in surface geometry and reflectance properties.

Printing, photocopying, and scanning processes degrade the image quality of a document. Statistical models of these degradation processes are crucial for document image understanding research. In this paper, we present a statistical methodology that can be used to validate local degradation models. This method is based on a nonparametric, two-sample permutation test. Another standard statistical device, the power function, is then used to choose between algorithm variables such as distance functions. Since the validation and the power function procedures are independent of the model, they can be used to validate any other degradation model. A method for comparing any two models is also described. It uses p-values associated with the estimated models to select the model that is closer to the real world.

This paper presents a complete system for scanning the geometry and surface color of a 3D object and for displaying realistic images of the object from arbitrary viewpoints. A stereo system with active light produces several views of dense range and color data. The data is registered and a surface that approximates the data is constructed. The surface estimate can be fairly coarse, as the appearance of fine detail is recreated by view-dependent texturing of the surface using color images.

Multiresolution analysis has been proposed as a basic tool supporting compression, progressive transmission, and level-of-detail control of complex meshes in a unified and theoretically sound way. We extend previous work on multiresolution analysis of meshes in two ways. First, we show how to perform multiresolution analysis of colored meshes by separately analyzing shape and color. Second, we describe efficient algorithms and data structures that allow us to incrementally construct lower resolution approximations to colored meshes from the geometry and color wavelet coefficients at interactive rates. We have integrated these algorithms in a prototype mesh viewer that supports progressive transmission, dynamic display at a constant frame rate independent of machine characteristics and load, and interactive choice of tradeoff between the amount of detail in geometry and color. The viewer operates as a helper application to Netscape, and can therefore be used to rapidly browse and di...

In computer graphics and geometric modeling, shapes are often represented by triangular meshes.With the advent of laser scanning systems, meshes of extreme complexity are rapidly becoming commonplace.Such meshes are notoriously expensive to store, transmit, render, and are awkward to edit.Multiresolution analysis offers a simple, unified, and theoretically sound approach to dealing with these problems.Lounsbery et al. have recently developed a technique for creating multiresolution representations for a restricted class of meshes with subdivision connectivity.Unfortunately, meshes encountered in practice typically do not meet this requirement.In this paper we present a method for overcoming the subdivision connectivity restriction, meaning that completely arbitrary meshes can now be converted to multiresolution form.The method is based on the approximation of an arbitrary initial mesh M by a mesh M J that has subdivision connectivity and is guaranteed to be within a specified tolerance.The key ingredient of our algorithm is the construction of a parametrization of M over a simple domain.We expect this parametrization to be of use in other contexts, such as texture mapping or the approximation of complex meshes by NURBS patches.

We present a general method for automatic reconstruction of accurate, concise, piecewise smooth surface models from scattered range data. The method can be used in a variety of applications such as reverse engineering—the automatic generation of CAD models from physical objects. Novel aspects of the method are its ability to model surfaces of arbitrary topological type and to recover sharp features such as creases and corners. The method has proven to be effective, as demonstrated by a number of examples using both simulated and real data.

We present a method for solving the following problem: Given a set of data points scattered in three dimensions and an initial triangular mesh M0, produce a mesh M, of the same topological type as M0, that fits the data well and has a small number of vertices.Our approach is to minimize an energy function that explicitly models the competing desires of conciseness of representation and fidelity to the data.We show that mesh optimization can be effectively used in at least two applications: surface reconstruction from unorganized points, and mesh simplification (the reduction of the number of vertices in an initially dense mesh of triangles).

Two basic principles for interactive visualization of high-dimensional data-focusing and linking-are discussed. Focusing techniques may involve selecting subsets, dimension reduction, or some more general manipulation of the layout information on the page or screen. A consequent of focusing is that each view only conveys partial information about the data and needs to be linked so that the information contained in individual views can be integrated into a coherent image of the data as a whole. Examples are given of how graphical data analysis methods based on focusing and linking are used in applications including linguistics, geographic information systems, time series analysis, and the analysis of multi-channel images arising in radiology and remote sensing.>