Algorithms for optical mapping.

Optical mapping is a novel technique for determining the restriction sites on a DNA molecule by directly observing a number of partially digested copies of the molecule under a light microscope. The problem is complicated by uncertainty as to the orientation of the molecules and by erroneous detection of cuts. In this paper we study the problem of constructing a restriction map based on optical mapping data. We give several variants of a polynomial reconstruction algorithm, as well as an algorithm that is exponential in the number of cut sites, and hence is appropriate only for small number of cut sites. We give a simple probabilistic model for data generation and for the errors and prove probabilistic upper and lower bounds on the number of molecules needed by each algorithm in order to obtain a correct map, expressed as a function of the number of cut sites and the error parameters. To the best of our knowledge, this is the first probabilistic analysis of algorithms for the problem. We also provide experimental results confirming that our algorithms are highly effective on simulated data.

An algorithm combining discrete and continuous methods for optical mapping.

Optical mapping is a novel technique for generating the restriction map of a DNA molecule by observing many single, partially digested copies of it, using fluorescence microscopy. The real-life problem is complicated by numerous factors: false positive and false negative cut observations, inaccurate location measurements, unknown orientations, and faulty molecules. We present an algorithm for solving the real-life problem. The algorithm combines continuous optimization and combinatorial algorithms applied to a nonuniform discretization of the data. We present encouraging results on real experimental data and on simulated data.

Physical mapping of chromosomes using unique probes.

The goal of physical mapping of the genome is to reconstruct a strand of DNA given a collection of overlapping fragments, or clones, from the strand. We present several algorithms to infer how the clones overlap, given data about each clone. We focus on data used to map human chromosomes 21 and Y, in which relatively short substrings, or probes, are extracted from the ends of clones. The substrings are long enough to be unique with high probability. The data we are given is an incidence matrix of clones and probes. In the absence of error, the correct placement can be found easily using a PQ-tree. The data are never free from error, however, and algorithms are differentiated by their performance in the presence of errors. We approach errors from two angles: by detecting and removing them, and by using algorithms that are robust in the presence of errors. We have also developed a strategy to recover noiseless data through an interactive process that detects anomalies in the data and retests questionable entries in the incidence matrix of clones and probes. We evaluate the effectiveness of our algorithms empirically, using simulated data as well as real data from human chromosome 21.

An algorithmic approach to multiple complete digest mapping.

Multiple Complete Digest (MCD) mapping is a method of determining the locations of restriction sites along a target DNA molecule. The resulting restriction map has many potential applications in DNA sequencing and genetics. In this work, we present a heuristic algorithm for fragment identification, a key step in the process of constructing an MCD map. Given measurements of the restriction fragment sizes from one or more complete digestions of each clone in a clone library covering the molecule to be mapped, the algorithm identifies groups of restriction fragments on different clones that correspond to the same region of the target DNA. Once these groups are correctly determined the desired map can be constructed by solving a system of simple linear inequalities. We demonstrate the effectiveness of our algorithm on real data provided by the Genome Center at the University of Washington.

An inhibitor of methionine aminopeptidase type-2, PPI-2458, ameliorates the pathophysiological disease processes of rheumatoid arthritis.

OBJECTIVE: To elucidate the role of methionine aminopeptidase type-2 (MetAP-2) in the clinical pathology of rheumatoid arthritis, arthritis was induced in rats by administration of peptidoglycan-polysaccharide (PG-PS). DESIGN: The inhibitor of MetAP-2, PPI-2458, was administered orally at 5 mg/kg every other day during 3 distinct phases of the disease. In vitro studies were performed to clarify in vivo findings. RESULTS: Ankle swelling was completely alleviated by MetAP-2 inhibition. Inhibition of MetAP-2 in blood and tissues correlated with protection against PG-PS-induced arthritis. Histopathology of the tarsal joints improved following PPI-2458 administration, including a significant improvement of bone structure. In in vitro studies, osteoclast formation and activity were inhibited by PPI-2458, a mechanism not previously attributed to MetAP-2 inhibition. CONCLUSIONS: The important role that MetAP-2 has in the pathophysiological disease processes of PG-PS arthritis provides a strong rationale for evaluating PPI-2458 as a disease modifying antirheumatic treatment for rheumatoid arthritis.

An algorithm for analysing probed partial digestion experiments.

A partial digestion of DNA (e.g. cosmid. Lambda, YAC, chromosome) is performed and the lengths of thoses fragments which hybridize to a labeled probe are measured using gel electrophoresis. We give an efficient algorithm that takes as input this experimental data and proposes one or more candidate solutions. Each solution designates the location of each restriction site and specifies the endpoints of each fragment. (Further experiments can then be designed to select the correct solution from this small set of candidates.) The algorithm works well even when the experiment gives inexact values for the lengths.

CLIFF: clustering of high-dimensional microarray data via iterative feature filtering using normalized cuts.

We present CLIFF, an algorithm for clustering biological samples using gene expression microarray data. This clustering problem is difficult for several reasons, in particular the sparsity of the data, the high dimensionality of the feature (gene) space, and the fact that many features are irrelevant or redundant. Our algorithm iterates between two computational processes, feature filtering and clustering. Given a reference partition that approximates the correct clustering of the samples, our feature filtering procedure ranks the features according to their intrinsic discriminability, relevance to the reference partition, and irredundancy to other relevant features, and uses this ranking to select the features to be used in the following round of clustering. Our clustering algorithm, which is based on the concept of a normalized cut, clusters the samples into a new reference partition on the basis of the selected features. On a well-studied problem involving 72 leukemia samples and 7130 genes, we demonstrate that CLIFF outperforms standard clustering approaches that do not consider the feature selection issue, and produces a result that is very close to the original expert labeling of the sample set.

Discovery of regulatory interactions through perturbation: inference and experimental design.

We present two methods to be used interactively to infer a genetic network from gene expression measurements. The predictor method determines the set of Boolean networks consistent with an observed set of steady-state gene expression profiles, each generated from a different perturbation to the genetic network. The chooser method uses an entropy-based approach to propose an additional perturbation experiment to discriminate among the set of hypothetical networks determined by the predictor. These methods may be used iteratively and interactively to successively refine the genetic network: at each iteration, the perturbation selected by the chooser is experimentally performed to generate a new gene expression profile, and the predictor is used to derive a refined set of hypothetical gene networks using the cumulative expression data. Performance of the predictor and chooser is evaluated on simulated networks with varying number of genes and number of interactions per gene.

Error checking and graphical representation of multiple-complete-digest (MCD) restriction-fragment maps.

Genetic and physical maps display the relative positions of objects or markers occurring within a target DNA molecule. In constructing maps, the primary objective is to determine the ordering of these objects. A further objective is to assign a coordinate to each object, indicating its distance from a reference end of the target molecule. This paper describes a computational method and a body of software for assigning coordinates to map objects, given a solution or partial solution to the ordering problem. We describe our method in the context of multiple-complete-digest (MCD) mapping, but it should be applicable to a variety of other mapping problems. Because of errors in the data or insufficient clone coverage to uniquely identify the true ordering of the map objects, a partial ordering is typically the best one can hope for. Once a partial ordering has been established, one often seeks to overlay a metric along the map to assess the distances between the map objects. This problem often proves intractable because of data errors such as erroneous local length measurements (e.g., large clone lengths on low-resolution physical maps). We present a solution to the coordinate assignment problem for MCD restriction-fragment mapping, in which a coordinated set of single-enzyme restriction maps are simultaneously constructed. We show that the coordinate assignment problem can be expressed as the solution of a system of linear constraints. If the linear system is free of inconsistencies, it can be solved using the standard Bellman-Ford algorithm. In the more typical case where the system is inconsistent, our program perturbs it to find a new consistent system of linear constraints, close to those of the given inconsistent system, using a modified Bellman-Ford algorithm. Examples are provided of simple map inconsistencies and the methods by which our program detects candidate data errors and directs the user to potential suspect regions of the map.

An algorithm combining discrete and continuous methods for optical mapping.

Optical mapping is a novel technique for generating the restriction map of a DNA molecule by observing many single, partially digested, copies of it, using fluorescence microscopy. The real-life problem is complicated by numerous factors: false positive and false negative cut observations, inaccurate location measurements, unknown orientations and faulty molecules. We present an algorithm for solving the real-life problem. The algorithm combines continuous optimization and combinatorial algorithms, applied to a non-uniform discretization of the data. We present encouraging results on real experimental data.

Estrogen receptor-beta expression in relation to the expression of luteinizing hormone receptor and cytochrome P450 enzymes in rat ovarian follicles.

Changes in mRNA expression for estrogen receptor (ER beta) in relation to mRNAs for LH receptor (LHr) and cytochrome P450 enzymes were examined in granulosa and theca cells from proestrous rat ovarian follicles. Of the 30 ovaries harvested from 15 adult rats, 24 were processed for in situ hybridization, and the remaining were used for reverse transcription-polymerase chain reaction. Messenger RNAs for ER beta, LHr, cytochrome P450 side-chain cleavage enzyme (P450(scc)), 17 alpha-hydroxylase (P450(c17)), aromatase (P450(arom)), and steroidogenic acute regulatory protein (StAR) were localized in cross sections of ovaries by in situ hybridization and quantified in granulosa and theca cell layers by a computer-image analyzing system. Ovarian follicles were classified as healthy or atretic. Healthy follicles were divided into four size groups: very small (40-100 microm), small (101-275 microm), medium (276-450 microm), and large (451-850 microm). Atretic follicles were divided into medium (276-450 microm) or large follicles (451-850 microm). A low level of ER beta mRNA expression was first detected in granulosa cells of very small healthy follicles, and the expression increased progressively up to medium-sized follicles. The expression of ER beta mRNA was highest (P < 0.01) in medium-sized follicles that was followed by a decrease (P < 0.01) in large follicles. Messenger RNAs for LHr, P450(scc), and P450(arom) were first detected in granulosa cells of medium-sized healthy follicles, while mRNAs for LHr, P450(scc), P450(c17), and StAR were first detected in theca cells associated with very small follicles. The highest expression of LHr, P450(scc), P450(c17), P450(arom), and StAR was seen in granulosa and/or theca cells of large healthy follicles. In atretic follicles, level of gene expression was relatively low in both granulosa and theca cells. In conclusion, stage-specific expression of ER beta mRNA was observed in granulosa cells during follicular development. The increased expression of ER beta and a concomitant initiation of LHr, P450(scc), and P450(arom) expression in granulosa cells of medium follicles may signify a role for estrogen in follicular development. Also, a strong correlation between ER beta mRNA expression in granulosa cells, and the expression of mRNAs for LHr, P450(scc), P450(c17), and StAR in theca cells associated with growing follicles suggests a possible role for estrogen in steroidogenesis.

Reconstructing chain functions in genetic networks.

Deciphering the mechanisms that control gene expression in the cell is a fundamental question in molecular biology. This task is complicated by the large number of possible regulation relations in the cell, and the relatively small amount of available experimental data. Recently, a new class of regulation functions called chain functions was suggested. Many signal transduction pathways can be accurately modeled by chain functions, and the restriction to chain functions greatly reduces the vast search space of regulation relations. In this paper we study the computational problem of reconstructing a chain function using a minimum number of experiments, in each of which only few genes are perturbed. We give optimal reconstruction schemes for several scenarios and show their application in reconstructing the regulation of galactose utilization in yeast.