US 7,039,621 B2Grant

System, method, and computer program product for representing object relationships in a multidimensional space

Issue Date:2006-05-02

•12 Claims

•12 Drawing Sheets

Abstract

A method and computer product is presented for mapping n-dimensional input patterns into an m-dimensional space so as to preserve relationships that may exist in the n-dimensional space. A subset of the input patterns is chosen and mapped into the m-dimensional space using an iterative nonlinear mapping process. A set of locally defined neural networks is created, then trained in accordance with the mapping produced by the iterative process. Additional input patterns not in the subset are mapped into the m-dimensional space by using one of the local neural networks. In an alternative embodiment, the local neural networks are only used after training and use of a global neural network. The global neural network is trained in accordance with the mapping produced by the iterative process. Input patterns are initially projected into the m-dimensional space using the global neural network. Local neural networks are then used to refine the results of the global network.

Metadata

Assignee

Johnson & Johnson Pharmaceutical Research & Development, L.L.C.

Inventors

Dimitris K. Agrafiotis
Dmitri N. Rassokhin
Victor S. Lobanov
F. Raymond Salemme

Application Information

Application Number:US 09/814,160

Filing Date:2001-03-22

Priority Date:2000-03-22

Art Unit:2192

Classifications

IPC:

G06E1/00

Patent Drawings (12 sheets)

Description

Cross-Reference to Related Applications

[0001] This application claims the benefit of U.S. Provisional Application No. 60/191,108, filed Mar. 22, 2000 (incorporated in its entirety herein by reference).

Background of the Invention

[0002] 1. Field of the Invention

[0003] The invention described herein relates to information representation, information cartography and data mining. The present invention also relates to pattern analysis and representation, and, in particular, representation of object relationships in a multidimensional space.

[0004] 2. Related Art

[0005] Reducing the dimensionality of large multidimensional data sets is an important objective in many data mining applications. High-dimensional spaces are sparse (Bellman, R. E., Adaptive Control Processes, Princeton University Press, Princeton (1961)), counter-intuitive (Wegman, E., J. Ann. Statist. 41:457–471 (1970)), and inherently difficult to understand, and their structure cannot be easily extracted with conventional graphical techniques. However, experience has shown that, regardless of origin, most multivariate data in R^dare almost never truly d-dimensional. That is, the underlying structure of the data is almost always of dimensionality lower than d. Extracting that structure into a low-dimensional representation has been the subject of countless studies over the past 50 years, and several techniques have been devised and popularized through the widespread availability of commercial statistical software. These techniques are divided into two main categories: linear and nonlinear.

[0006] Perhaps the most common linear dimensionality reduction technique is principal component analysis, or PCA (Hotelling, H., J. Edu. Psychol. 24:417–441; 498–520 (1933)). PCA reduces a set of partially cross-correlated data into a smaller set of orthogonal variables with minimal loss in the contribution to variation. The method has been extensively tested and is well-understood, and several effective algorithms exist for computing the projection, ranging from singular value decomposition to neural networks (Oja, E., Subspace Methods of Pattern Recognition, Research Studies Press, Letchworth, England (1983); Oja, E., Neural Networks 5:927–935 (1992); Rubner, J., and Tavan, P., Europhys. Lett. 10:693–698 (1989)). PCA makes no assumptions about the probability distributions of the original variables, but is sensitive to outliers, missing data, and poor correlations due to poorly distributed variables. More importantly, the method cannot deal effectively with nonlinear structures, curved manifolds, and arbitrarily shaped clusters.

[0007] A more general methodology is Friedman's exploratory projection pursuit (EPP) (Friedman, J. H., and Tukey, J. W., IEEE Trans. Computers 23:881–890 (1974); Friedman, J. H., J. Am. Stat. Assoc. 82:249–266 (1987)). This method searches multidimensional data sets for interesting projections or views. The “interestingness” of a projection is typically formulated as an index, and is numerically maximized over all possible projections of the multivariate data. In most cases, projection pursuit aims at identifying views that exhibit significant clustering and reveal as much of the non-normally distributed structure in the data as possible. The method is general, and includes several well-known linear projection techniques as special cases, including principal component analysis (in this case, the index of interestingness is simply the sample variance of the projection). Once an interesting projection has been identified, the structure that makes the projection interesting may be removed from the data, and the process can be repeated to reveal additional structure. Although projection pursuit attempts to express some nonlinearities, if the data set is high-dimensional and highly nonlinear it may be difficult to visualize it with linear projections onto a low-dimensional display plane, even if the projection angle is carefully chosen.

[0008] Several approaches have been proposed for reproducing the nonlinear structure of higher-dimensional data spaces. The best-known techniques are self-organizing maps, auto-associative neural networks, multidimensional scaling, and nonlinear mapping.

[0009] Self-organizing maps or Kohonen networks (Kohonen, T., Self-Organizing Maps, Springer-Verlag, Heidelberg (1996)) were introduced by Kohonen in an attempt to model intelligent information processing, i .e. the ability of the brain to form reduced representations of the most relevant facts without loss of information about their interrelationships. Kohonen networks belong to a class of neural networks known as competitive learning or self-organizing networks. Their objective is to map a set of vectorial samples onto a two-dimensional lattice in a way that preserves the topology and density of the original data space. The lattice points represent neurons which receive identical input, and compete in their activities by means of lateral interactions. The main application of self-organizing maps is in visualizing complex multi-variate data on a 2-dimensional plot, and in creating abstractions reminiscent of these obtained from clustering methodologies. These reduced representations can subsequently be used for a variety of pattern recognition and classification tasks.

[0010] Another methodology is that of auto-associative neural networks (DeMers, D., and Cottrell, G., Adv. Neural Info. Proces. Sys. 5:580–587 (1993); Garrido, L., et al., Int. J. Neural Sys. 6:273–282 (1995)). These are multi-layer feed-forward networks trained to reproduce their inputs as desired outputs. They consist of an input and an output layer containing as many neurons as the number of input dimensions, and a series of hidden layers having a smaller number of units. In the first part of the network, each sample is reorganized, mixed, and compressed into a compact representation encoded by the middle layer. This representation is then decompressed by the second part of the network to reproduce the original input. Auto-associative networks can be trained using conventional back-propagation or any other related technique available for standard feed-forward architectures. A special version of the multilayer perceptron, known as a replicator network (Hecht-Nielsen, R., Science 269:1860–1863 (1995)), has been shown to be capable of representing its inputs in terms of their “natural coordinates”. These correspond to coordinates in an m-dimensional unit cube that has been transformed elastically to fit the distribution of the data. Although in practice it may be difficult to determine the inherent dimensionality of the data, the method could, in theory, be used for dimensionality reduction using a small value of m.

[0011] The aforementioned techniques can be used only for dimension reduction. A more broadly applicable method is multidimensional scaling (MDS) or nonlinear mapping (NLM). This approach emerged from the need to visualize a set of objects described by means of a similarity or distance matrix. The technique originated in the field of mathematical psychology (see Torgeson, W. S., Psychometrika, 1952, and Kruskal, J. B. Phychometrika, 1964, both of which are incorporated by reference in their entirety), and has two primary applications: 1) reducing the dimensionality of high-dimensional data in a way that preserves the original relationships of the data objects, and 2) producing Cartesian coordinate vectors from data supplied directly in the form of similarities or proximities, so that they can be analyzed with conventional statistical and data mining techniques.

[0012] Given a set of k objects, a symmetric matrix, r_ij, of relationships between these objects, and a set of images on a m-dimensional display plane {y_i, i=1, 2, . . . , k; y_i∈R^m}, the problem is to place y_ionto the plane in such a way that their Euclidean distances d_ij=∥y_i−y_j∥ approximate as closely as possible the corresponding values r_ij. The quality of the projection is determined using a loss function such as Kruskal's stress:

[0013]

\begin{matrix} S = \sqrt{\frac{\sum_{i < j} {(d_{ij} - r_{ij})}^{2}}{\sum_{i < j} r_{ij}^{2}}} & (1) \end{matrix}

which is numerically minimized in order to find the optimal configuration. The actual embedding is carried out in an iterative fashion by: 1) generating an initial set of coordinates y_i, 2) computing the distances d_ij, 3) finding a new set of coordinates y_iusing a steepest descent algorithm such as Kruskal's linear regression or Guttman's rank-image permutation, and 4) repeating steps 2 and 3 until the change in the stress function falls below some predefined threshold.

[0014] A particularly popular implementation is Sammon's nonlinear mapping algorithm (Sammon, J. W. IEEE Trans. Comp., 1969). This method uses a modified stress function:

[0015]

\begin{matrix} E = \frac{\sum_{i < j}^{k} \frac{{[r_{ij} - d_{ij}]}^{2}}{r_{ij}}}{\sum_{i < j}^{k} r_{ij}} & (2) \end{matrix}

which is minimized using steepest descent. The initial coordinates, y_i, are determined at random or by some other projection technique such as principal componenet analysis, and are updated using Eq. 3:
y_ij(t+1)=y_ij(t)−λΔ_y(t) (3)
where t is the iteration number and λ is the learning rate parameter, and

[0016]

\begin{matrix} Δ_{ij} (t) = \frac{\frac{\partial E (t)}{\partial y_{ij} (t)}}{\langle \frac{\partial^{2} E (t)}{\partial {y_{ij} (t)}^{2}} \rangle} & (4) \end{matrix}

[0017] There is a wide variety of MDS algorithms involving different error functions and optimization heuristics, which are reviewed in Schiffman, Reynolds and Young, Introduction to Multidimensional Scaling, Academic Press, New York (1981); Young and Hamer, Multidimensional Scaling: History, Theory and Applications, Erlbaum Associates, Inc., Hillsdale, N.J. (1987); Cox and Cox, Multidimensional Scaling, Number 59 in Monographs in Statistics and Applied Probability, Chapman-Hall (1994), and Borg, I., Groenen, P., Modem Multidimensional Scaling, Springer-Verlag, New York, (1997). The contents of these publications are incorporated herein by reference in their entireties. Different forms of NLM will be discussed in greater detail below.

[0018] Unfortunately, the quadratic nature of the stress function (Eqs. 1 and 2, and their variants) make these algorithms impractical for large data sets containing more than a few hundred to a few thousand items. Several attempts have been devised to reduce the complexity of the task. Chang and Lee (Chang, C. L., and Lee, R. C. T., IEEE Trans. Syst., Man, Cybern., 1973, SMC-3, 197–200) proposed a heuristic relaxation approach in which a subject of the original objects (the frame) are scaled using a Sammon-like methodology, and the remaining objects are then added to the map by adjusting their distances to the objects in the frame. An alternative approach proposed by Pykett (Pykett, C. E., Electron. Lett., 1978, 14, 799–800) is to partition the data into a set of disjoint clusters, and map only the cluster prototypes, i.e. the centroids of the pattern vectors in each class. In the resulting two-dimensional plots, the cluster prototypes are represented as circles whose radii are proportional to the spread in their respective classes. Lee, Slagle and Blum (Lee, R. C. Y., Slagle, J. R., and Blum, H., IEEE Trans. Comput., 1977, C-27, 288–292) proposed a triangulation method which restricts attention to only a subset of the distances between the data samples. This method positions each pattern on the plane in a way that preserves its distances from the two nearest neighbors already mapped. An arbitrarily selected reference pattern may also be used to ensure that the resulting map is globally ordered. Biswas, Jain and Dubes (Biswas, G., Jain, A. K., and Dubes, R. C., IEEE Trans. Pattern Anal. Machine Intell., 1981, PAMI-3(6), 701–708) later proposed a hybrid approach which combined the ability of Sammon's algorithm to preserve global information with the efficiency of Lee's triangulation method. While the triangulation can be computed quickly compared to conventional MDS methods, it tries to preserve only a small fraction of relationships, and the projection may be difficult to interpret for large data sets.

[0019] The methods described above are iterative in nature, and do not provide an explicit mapping function that can be used to project new, unseen patterns in an efficient manner. The first attempt to encode a nonlinear mapping as an explicit function is due to Mao and Jain (Mao, J., and Jain, A. K., IEEE Trans. Neural Networks 6(2):296–317 (1995)). They proposed a 3-layer feed-forward neural network with n input and m output units, where n and m are the number of input and output dimensions, respectively. The system is trained using a special back-propagation rule that relies on errors that are functions of the inter-pattern distances. However, because only a single distance is examined during each iteration, these networks require a very large number of iterations and converge extremely slowly.

[0020] An alternative methodology is to employ Sammon's nonlinear mapping algorithm to project a small random sample of objects from a given population, and then “learn” the underlying nonlinear transform using a multilayer neural network trained with the standard error back-propagation algorithm or some other equivalent technique (see for example, Haykin, S. Neural Networks: A Comprehensive Foundation. Prentice-Hall, 1998). Once trained, the neural network can be used in a feed-forward manner to project the remaining objects in the plurality of objects, as well as new, unseen objects. Thus, for a nonlinear projection from n to m dimensions, a standard 3-layer neural network with n input and m output units is used. Each n-dimensional object is presented to the input layer, and its coordinates on the m-dimensional nonlinear map are obtained by the respective units in the output layer (Pal, N. R. Eluri, V. K., IEEE Trans. Neural Net., 1142–1154 (1998)).

[0021] The distinct advantage of this approach is that it captures the nonlinear mapping relationship in an explicit function, and allows the scaling of additional patterns as they become available, without the need to reconstruct the entire map. It does, however, rely on conventional MDS methodologies to construct the nonlinear map of the training set, and therefore the method is inherently limited to relatively small samples.

[0022] Hence there is a need for a method that can efficiently process large data sets, e.g., data sets containing hundreds of thousands to millions of items.

[0023] Moreover, just like Mao and Jain (Mao, J., and Jain, A. K., IEEE Trans. Neural Networks 6(2):296–317 (1995)) and Pal and Eluri (Pal, N. R. Eluri, V. K., IEEE Trans. Neural Net., 1142–1154 (1998)), a method is needed that is incremental in nature, and allows the mapping of new samples as they become available, without the need to reconstruct an entire map.

Summary of the Invention

[0024] A method and computer product is presented for mapping input patterns of high dimensionality into a lower dimensional space so as to preserve the relationships between these patterns in the higher dimensional space. A subset of the input patterns is chosen and mapped into the lower dimensional space using an iterative process based on subset refinements. A set of local regions is defined using a clustering methodology, and a local neural network is associated with each of these regions, and trained in accordance with the mapping obtained from the iterative process. Additional input patterns not in the subset are mapped into the lower dimensional space by using one of the local neural networks. In an alternative embodiment, the local neural networks are only used after training and use of a global neural network. The global neural network is trained in accordance with the results of the mapping produced by the iterative process. Input patterns are fed into the global neural network, resulting in patterns in the lower dimensional space. Local neural networks are then used to refine the results of the global network.

[0025] The method and computer product described herein permits the mapping of massive data sets from a higher dimensional space to a lower dimensional space. Moreover, the method allows the mapping of new input patterns as they become available, without the need to reconstruct an entire map.

[0026] The foregoing and other features and advantages of the invention will be apparent from the following, more particular description of a preferred embodiment of the invention, as illustrated in the accompanying drawings.

Brief Description of the Drawings/Figures

[0027] FIG. 1 illustrates possibilities for a single hypothetical pairwise relationship and distances of corresponding objects on a nonlinear map.

[0028] FIG. 2 is a flowchart illustrating the phases of the method of the invention.

[0029] FIG. 3 is a flowchart illustrating the training phase of the invention, according to an embodiment.

[0030] FIG. 4 is a flowchart illustrating the use of a fuzzy clustering methodology in the selection of reference patterns, according to an embodiment of the invention.

[0031] FIG. 5 illustrates the concept of Voronoi cells, as used in an embodiment of the invention.

[0032] FIG. 6 is a flowchart illustrating the projection of input patterns, according to an embodiment of the invention.

[0033] FIG. 7 illustrates the operation of local neural networks, according to an embodiment of the invention.

[0034] FIG. 8 is a flowchart illustrating the training phase of the invention, according to an alternative embodiment.

[0035] FIG. 9 is a flowchart illustrating the projection of input patterns, according to an alternative embodiment of the invention.

[0036] FIG. 10 illustrates the operation of global and local neural networks, according to an alternative embodiment of the invention.

[0037] FIG. 11 illustrates a computing environment within which the invention can operate.

Detailed Description of the Invention

[0038] A preferred embodiment of the present invention is now described with reference to the figures where like reference numbers indicate identical or functionally similar elements. Also in the figures, the left most digit of each reference number corresponds to the figure in which the reference number is first used. While specific configurations and arrangements are discussed, it should be understood that this is done for illustrative purposes only. A person skilled in the relevant art will recognize that other configurations and arrangements can be used without departing from the spirit and scope of the invention. It will be apparent to a person skilled in the relevant art that this invention can also be employed in a variety of other devices and applications.

I. Introduction

A. Overview

[0039] A neural network architecture for reducing the dimensionality of very large data sets is presented here. The method is rooted on the principle of probability sampling, i.e. the notion that a small number of randomly chosen members of a given population will tend to have the same characteristics, and in the same proportion, with the population as a whole. The approach employs an iterative algorithm based on subset refinements to nonlinearly map a small random sample which reflects the overall structure of the data, and then “learns” the underlying nonlinear transform using a set of distributed neural networks, each specializing in a particular domain of the feature space. The partitioning of the data space can be carried out using a clustering methodology. This local approach eliminates a significant portion of the imperfection of the nonlinear maps produced by a single multi-layer perceptron, and does so without a significant computational overhead. The proposed architecture is general and can be used to extract constraint surfaces of any desired dimensionality.

[0040] The following section discusses methods that can be used to nonlinearly map a random subset of the data.

B. Nonlinear Mapping Using Subset Refinements

- [0041] 1. Overview

[0042] A nonlinear mapping algorithm that is well suited for large data sets is presented in U.S. patent application Ser. No. 09/303,671, filed May 3, 1999, titled, “Method, System and Computer Program Product for Nonlinear Mapping of Multidimensional Data”, and U.S. patent application Ser. No. 09/073,845, filed May 7, 1998, titled, “Method, System and Computer Program Product for Representing Proximity Data in a Multidimensional Space”. This approach is to use iterative refinement of coordinates based on partial or stochastic errors.

[0043] The method uses a self-organizing principle to iteratively refine an initial (random or partially ordered) configuration of objects by analyzing only a subset of objects and their associated relationships at a time. The relationship data may be complete or incomplete (i.e. some relationships between objects may not be known), exact or inexact (i.e. some or all relationships may be given in terms of allowed ranges or limits), symmetric or asymmetric (i.e. the relationship of object A to object B may not be the same as the relationship of B to A) and may contain systematic or stochastic errors.

[0044] The relationships between objects may be derived directly from observation, measurement, a priori knowledge, or intuition, or may be determined directly or indirectly using any suitable technique for deriving such relationships.

[0045] The invention determines the coordinates of a plurality of objects on the m-dimensional nonlinear map by:

[0046] (1) placing the objects on the m-dimensional nonlinear map;

[0047] (2) selecting a subset of the objects, wherein the selected subset of objects includes associated relationships between objects in the selected subset;

[0048] (3) revising the coordinate(s) of one or more objects in the selected subset of objects on the m-dimensional nonlinear map based on the relationship(s) between some of these objects and their corresponding distance(s) on the nonlinear map;

[0049] (4) repeating steps (2) and (3) for additional subsets of objects from the plurality of objects.

[0050] In one embodiment, subsets of objects can be selected randomly, semi-randomly, systematically, partially systematically, etc. As subsets of objects are analyzed and their distances on the nonlinear map are revised, the set of objects tends to self-organize.

[0051] In a preferred embodiment, the invention iteratively analyzes a pair of objects at a time, that is, step (2) is carried out by selecting a pair of objects having an associated pairwise relationship. Pairs of objects can be selected randomly, semi-randomly, systematically, partially systematically, etc. Novel algorithms and techniques for pairwise analysis are provided in the sections below. This embodiment is described for illustrative purposes only and is not limiting.

[0052] 2. Pairwise Relationship Matrices without Uncertainties

- [0053] a. Full Pairwise Relationship Matrices without Uncertainties

[0054] The discussion in this section assumes that all pairwise relationships are known, and they are all exact. In a preferred embodiment, the method starts with an initial configuration of points generated at random or by some other procedure such as principal component analysis. This initial configuration is then continuously refined by repeatedly selecting two objects, i, j, at random, and modifying their coordinates on the nonlinear map according to Eq. 5:
y_i(t+1)=ƒ(t, y_i(t),y_j(t),r_ij) (5)
where t is the current iteration, y_i(t) and y_j(t) are the current coordinates of the i-th and j-th objects on the nonlinear map, y_i(t+1) are the new coordinates of the i-th object on the nonlinear map, and r_ijis the relationship between the i-th and j-th objects. ƒ(.) in Eq. 5 above can assume any functional form. Ideally, this function should try to minimize the difference between the distance on the nonlinear map and the actual relationship between the i-th and j-th objects. For example, ƒ(.) may be given by Eq. 6:

[0055]

\begin{matrix} y_{i} (t + 1) = 0.5 λ (t) \frac{r_{ij} - d_{ij} (t)}{d_{ij} (t)} (y_{i} (t) - y_{j} (t)) & (6) \end{matrix}

where t is the iteration number, d_ij=∥y_i(t)−y_j(t)∥, and λ(t) is an adjustable parameter, referred to hereafter as the “learning rate”. This process is repeated for a fixed number of cycles, or until some global error criterion is minimized within some prescribed tolerance. A large number of iterations are typically required to achieve statistical accuracy.

[0056] The method described above is generally reminiscent of the error back-propagation procedure for training artificial neural networks described in Werbos, Beyond Regression: New Tools for Prediction and Analysis in the Behavioral Sciences, PhD Thesis, Harvard University, Cambridge, Mass. (1974), and Rumelhart and McClell and, Eds., Parallel Distributed Processing: Explorations in the Microstructure of Cognition, Vol. 1, MIT Press, Cambridge, Mass. (1986), both of which are incorporated herein by reference in their entireties.

[0057] The learning rate λ(t) in EQ. 6 plays a key role in ensuring convergence. If λ is too small, the coordinate updates are small, and convergence is slow. If, on the other hand, λ is too large, the rate of learning may be accelerated, but the nonlinear map may become unstable (i.e. oscillatory). Typically, λ ranges in the interval [0, 1] and may be fixed, or it may decrease monotonically during the refinement process. Moreover, λ may also be a function of i, j, r_ij, and/or d_ij, and can be used to apply different weights to certain objects, relationships, distances and/or relationship or distance pairs. For example, λ may be computed by Eq. 7:

[0058]

\begin{matrix} λ (t) = (λ_{\min} + t \frac{λ_{\max} - λ_{\min}}{T}) \frac{1}{1 + {ar}_{ij}} or Eq. 8: & (7) \\ λ (t) = (λ_{\min} + t \frac{λ_{\max} - λ_{\min}}{T}) ⅇ^{- {ar}_{ij}} & (8) \end{matrix}

where λ_maxand λ_minare the (unweighted) starting and ending learning rates such that λ_max, λ_min, ∈[0,1], T is the total number of refinement steps (iterations), t is the current iteration number, and α is a constant scaling factor. EQ. 7 and 8 have the effect of decreasing the correction at large separations (weak relationships), thus creating a nonlinear map which preserves strong relationships (short distances) more faithfully than weak ones. Weighting is discussed in greater detail below.

[0059] One of the main advantages of this approach is that it makes partial refinements possible. It is often sufficient that the pairwise similarities are represented only approximately to reveal the general structure and topology of the data. Unlike traditional MDS, this approach allows very fine control of the refinement process. Moreover, as the nonlinear map self-organizes, the pairwise refinements become cooperative, which partially alleviates the quadratic nature of the problem.

[0060] The embedding procedure described above does not guarantee convergence to the global minimum (i.e., the most faithful embedding in a least-squares sense). If so desired, the refinement process may be repeated a number of times from different starting configurations and/or random number seeds.

[0061] The general algorithm described above can also be applied when the pairwise similarity matrix is incomplete, i.e. when some of the pairwise similarities are unknown, when some of the pairwise similarities are uncertain or corrupt, or both of the above. These cases are discussed separately below.

- [0062] b. Sparse Pairwise Relationship Matrices without Uncertainties

[0063] The general algorithm described above can also be applied when the pairwise relationship matrix is incomplete, i.e. when some of the pairwise relationships are unknown. In this case, a similar algorithm to the one described above can be used, with the exception that the algorithm iterates over pairs of objects for which the relationships are known. In this case, the algorithm identifies configurations in space that satisfy the known pairwise relationships; the unknown pairwise relationships adapt during the course of refinement and eventually assume values that lead to a satisfactory embedding of the known relationships.

[0064] Depending on the number of missing data, there may be more than one satisfactory embeddings (mappings) of the original relationship matrix. In this case, different configurations (maps) may be derived from different starting configurations or random number seeds. In some applications such as searching the conformational space of molecules, this feature provides a significant advantage over some alternative techniques. All variants of the original algorithm (see Sections below) can be used in this context.

[0065] 3. Pairwise Relationship Matrices with Bounded Uncertainties

[0066] The general algorithm described above can also be applied when the pairwise relationships contain bounded uncertainties, i.e. when some of the pairwise relationships are only known to within certain fixed tolerances (for example, the relationships are known to lie within a range or set of ranges with prescribed upper and lower bounds). In this case, a similar algorithm to the one described above can be used, with the exception that the distances on the nonlinear map are corrected only when the corresponding objects lie outside the prescribed bounds. For example, assume that the relationship between two objects, i and j, is given in terms of an upper and lower bound, r_maxand r_min, respectively. When this pair of objects is selected during the course of the refinement, the distance of the objects on the nonlinear map is computed, and denoted as d_ij. If d_ijis larger than r_max, the coordinates of the objects are updated using r_maxas the target distance (Eq. 9):
y_i(t+1)=ƒ(t,y_j(t),y_j(t),r_max) (9)

[0067] Conversely, if d_ijis smaller than r_minthe coordinates of the objects are updated using r_minin as the target distance (Eq. 10):
y_i(t+1)=ƒ(t,y_i(t),y_j(t),r_min) (10)
If d_ijlies between the upper and lower bounds (i.e. if r_min≠d_ij≠r_max), no correction is made. In other words, the algorithm attempts to match the upper bound if the current distance between the objects is greater than the upper bound, or the lower bound if the current distance between the objects is lower than the lower bound. If the distance between the objects lies within the upper and lower bounds, no correction is made.

[0068] This algorithm can be extended in the case where some of the pairwise relationships are given by a finite set of allowed discrete values, or by a set of ranges of values, or some combination thereof. For the purposes of the discussion below, we consider discrete values as ranges of zero width (e.g. the discrete value of 2 can be represented as the range [2,2]).

[0069] Various possibilities for a single hypothetical pairwise relationship and the current distance of the corresponding objects on the nonlinear map are illustrated in FIG. 1, where shaded areas 110, 112 and 114 denote allowed ranges for a given pairwise relationship. Distances d1–d5 illustrate 5 different possibilities for the current distance between the corresponding objects on the nonlinear map. Arrows 116, 118, 120 and 122 indicate the direction of the correction that should be applied on the objects on the map. Arrows 118 and 122 point to the left, indicating that the coordinates of the associated objects on the nonlinear map should be updated so that the objects come closer together. Arrows 116 and 120 point to the right, indicating that the coordinates of the associated objects should be updated so that the objects become more distant.

[0070] As in the case of a single range, if the current distance of a selected pair of objects on the nonlinear map lies within any of the prescribed ranges, no coordinate update takes place (i.e., case d1 in FIG. 1). If not, the correction is applied using the nearest range boundary as the target distance (i.e., cases d2–d5 in FIG. 1). For example, if the relationship between a given pair of objects lies in the ranges [1,2], [3,5]and [6,7 ]and their current distance on the nonlinear map is 2.9 (d5 in FIG. 1), the correction takes place using 3 as the target distance (r_ij) in Eq. 5. If, however, the current distance is 2.1, the coordinates are updated using 2 as the target distance (r_ij) in Eq. 5.

[0071] This deterministic criterion may be replaced by a stochastic or probabilistic one in which the target distance is selected either randomly or with a probability that depends on the difference between the current distance and the two nearest range boundaries. In the example described above (d5 in FIG. 1), a probabilistic choice between 2 and 3 as a target distance could be made, with probabilities of, for example, 0.1 and 0.9, respectively (that is, 2 could be selected as the target distance with probability 0.1, and 3 with probability 0.9). Any method for deriving such probabilities can be used. Alternatively, either 2 or 3 could be chosen as the target distance at random.

[0072] For example, bounded uncertainties in the pairwise relationships may represent stochastic or systematic errors or noise associated with a physical measurement, and can, in general, differ from one pairwise relationship to another. A typical example are the Nuclear Overhauser Effects (NOE's) in multidimensional Nuclear Magnetic Resonance spectrometry. Alternatively, the uncertainty may result from multiple measurements of a given relationship.

[0073] An alternative algorithm for dealing with uncertainties is to reduce the magnitude of the correction for pairs of objects whose relationship is thought to be uncertain. In this scheme, the magnitude of the correction, as determined by the learning rate in Eq. 8, for example, is reduced for pairwise relationships which are thought to be uncertain. The magnitude of the correction may depend on the degree of uncertainty associated with the corresponding pairwise relationship (for example, the magnitude of the correction may be inversely proportional to the uncertainty associated with the corresponding pairwise relationship). If the existence and/or magnitude of the errors is unknown, then the errors can be determined automatically by the algorithm.

[0074] 4. Pairwise Relationship Matrices with Unbounded Uncertainties

[0075] The ideas described in the preceding Sections can be applied when some of the pairwise relationships are thought to contain corrupt data, that is when some of the pairwise relationships are incorrect and bear essentially no relationship to the actual values. In this case, “problematic” relationships can be detected during the course of the algorithm, and removed from subsequent processing. In other words, the objective is to identify the corrupt entries and remove them from the relationship matrix. This process results in a sparse relationship matrix, which can be refined using the algorithm in Section 2.a above.

[0076] 5. Modifications of the Basic Algorithm

[0077] In many cases, the algorithm described above may be accelerated by pre-ordering the data using a suitable statistical method. For example, if the proximities are derived from data that is available in vectorial or binary form, the initial configuration of the points on the nonlinear map may be computed using principal component analysis. In a preferred embodiment, the initial configuration may be constructed from the first m principal components of the feature matrix (i.e. the m latent variables which account for most of the variance in the data). This technique can have a profound impact on the speed of refinement. Indeed, if a random initial configuration is used, a significant portion of the training time is spent establishing the general structure and topology of the nonlinear map, which is typically characterized by large rearrangements. If, on the other hand, the input configuration is partially ordered, the error criterion can be reduced relatively rapidly to an acceptable level.

[0078] If the data is highly clustered, by virtue of the sampling process low-density areas may be refined less effectively than high-density areas. In one embodiment, this tendency may be partially compensated by a modification to the original algorithm, which increases the sampling probability in low-density areas. This type of biased sampling may be followed with regular, unbiased sampling, and this process may be repeated any number of times in any desired sequence.

[0079] Generally, the basic algorithm does not distinguish weak from strong relationships (short-range and long-range distances, respectively). One method to ensure that strong relationships are preserved more faithfully than weak relationships is to weight the coordinate update in EQ. 5 (or, equivalently, the learning rate λ in EQ. 7 and 8) by a scaling factor that is inversely proportional to the strength (magnitude) of the relationship

[0080] An alternative (and complementary) approach is to ensure that objects at close separation are sampled more extensively than objects at long separation. For example, an alternating sequence of global and local refinement cycles, similar to the one described above, can be employed. In this embodiment, a phase of global refinement is initially carried out, after which, the resulting nonlinear map is partitioned into a regular grid. The points (objects) in each cell of the grid are then subjected to a phase of local refinement (i.e. only objects from within the same cell are compared and refined). Preferably, the number of sampling steps in each cell should be proportional to the number of objects contained in that cell. This process is highly parallelizable. This local refinement phase is then followed by another global refinement phase, and the process is repeated for a prescribed number of cycles, or until the embedding error is minimized within a prescribed tolerance. Alternatively, the grid method may be replaced by another suitable method for identifying proximal points, such as clustering, for example.

[0081] The methods described herein may be used for incremental mapping. That is, starting from an organized nonlinear map of a set of objects, a new set of objects may be added without modification of the original map. In an exemplary embodiment, the new set of objects may be “diffused” into the existing map, using a modification of the basic algorithm described above. In particular, Eq. 5 and 6 can be used to update only the additional objects. In addition, the sampling procedure ensures that the selected pairs contain at least one object from the new set. That is, two objects are selected at random so that at least one of these objects belongs to the new set. Alternatively, each new object may be added independently using the approach described above.

II. Method

[0082] A. Nonlinear Mapping Networks—Algorithm I

[0083] The process described herein uses the iterative nonlinear mapping algorithm described in Section II to multidimensionally scale a small random sample of a set of input patterns of dimensionality n, and then “learns” the underlying nonlinear transform using an artificial neural network. For a nonlinear projection from n to m dimensions, a simple 3-layer network with n input and m output units can be employed. The network is trained to reproduce the input/output coordinates produced by the iterative algorithm, and thus encodes the mapping in its synaptic parameters in a compact, analytical manner. Once trained, the neural network can be used in a feed-forward fashion to project the remaining members of the input set, as well as new, unseen samples with minimal distortion.

[0084] The method of the invention is illustrated generally in FIG. 2. The method begins at step 205. In step 210, the training of a neural network takes place, where the training is based on the results (i.e., the inputs and outputs) of the iterative algorithm. In step 215, points in Rⁿare projected into R^mby a feed-forward pass through the trained neural network The process concludes with step 220.

[0085] B. Local Nonlinear Mapping Networks—Algorithm II

[0086] The embodiment of the invention described in this section represents a variation of the above algorithm. This approach is based on local learning. Instead of using a single “global” network to perform the nonlinear mapping across the entire input data space Rⁿ, this embodiment partitions the space into a set of Voronoi polyhedra, and uses a separate “local” network to project the patterns in each partition. Given a set of reference points P={P₁, P₂, . . . } in Rⁿ, a Voronoi polyhedron (or Voronoi cell), v(p), is a convex polytope associated with each reference point p which contains all the points in Rⁿthat are closer to p than any other point in P:
v(p)={x∈Rⁿ|d(x,p)≦d(x,q)∀p,q∈P,p≠q} (11)
where d( ) is a distance function. In an embodiment of the invention, d( ) is the Euclidean distance function. Voronoi cells partition the input data space Rⁿinto local regions “centered” at the reference points P, also referred to as centroids. Hereafter, the local networks associated with each Voronoi cell are said to be centered at the points P, and the distance of a point in Rⁿfrom a local network will refer to the distance of that point from the network's center.

[0087] The training phase involves the following general steps: a training set is extracted from the set of input patterns and mapped using the iterative nonlinear mapping algorithm described in Section II. A set of reference points in the input space Rⁿis then selected, and the objects comprising the training set are partitioned into disjoint sets containing the patterns falling within the respective Voronoi cells. Patterns that lie on the sides and vertices of the Voronoi cells (i.e. are equidistant to two or more points in P), are arbitrarily assigned to one of the cells. A local network is then assigned to each cell, and is trained to reproduce the input/output mapping of the input patterns in that cell. While the direct nonlinear map is obtained globally, the networks are trained locally using only the input patterns within their respective Voronoi partitions. Again, simple 3-layer perceptrons with n input and m output units can be employed, where n and m are the dimensionalities of the input and output spaces, respectively.

[0088] The training phase of the method of the invention therefore involves the following steps as illustrated in FIG. 3. The training phase begins at step 305. In step 310, a random set of points {x_i, i=1,2, . . . , k; x_i∈Rⁿ} is extracted from the set of input patterns. In step 315, the points x_iare mapped from Rⁿto R^musing the iterative nonlinear mapping algorithm described in Section II (x_i→y_i, i=1,2, . . . , k, x_i∈R^m). This mapping serves to define a training set T of ordered pairs (x_i, y_i), T={(x_i, y_i), i=1,2, . . . , k}.

[0089] In step 320, a set of reference points P={c₁, i=1,2, . . . c; c₁∈Rⁿ} is determined. In an embodiment of the invention, the reference points c_iare determined using a clustering algorithm described in greater detail below. In step 325, the training set T is partitioned into c disjoint clusters based on the distance of each point x_ifrom each reference point. The set of disjoint clusters is denoted {C_j={(x_j, y_i): d(x_i, c_j)≦d(x_i, c_k)} for all k≠j; j=1,2, . . . , c; i=1,2, . . . , k}. In step 330, c independent local networks {Net_i^L, i=1,2, . . . , c} are trained with the respective training subsets C_iderived in step 325. The training phase concludes with step 335.

[0090] Clearly, an important choice to be made concerns the partitioning. In general, the reference points c_i(determined in step 320) should be well distributed and should produce balanced partitions that contain a comparable number of training patterns. This is necessary in order to avoid the creation of poorly optimized networks due to an insufficient number of training cases. In one embodiment, described here, the reference points c_ican be determined using the fuzzy clustering means (FCM) algorithm (Bezdek, J. C., Pattern Recognition with Fuzzy Objective Function Algorithms. Plenum Press, 1981). The FCM algorithm uses the probabilistic constraint that the sum of the memberships of a data point over all clusters must be equal to 1, and has been most successful in situations where the final objective is a crisp decision, as is the case in the problem at hand.

[0091] The FCM algorithm attempts to minimize the objective function:

[0092]

\begin{matrix} J_{q} = \sum_{j = 1}^{C} \sum_{i = 1}^{N} m_{ij}^{q} d^{2} (x_{i}, c_{j}) & (12) \end{matrix}

over a set of points x_i, i=1,2, . . . , N, with respect to the fuzzy degrees of membership m_ij, the “fuzziness” index q, and the cluster centroids c_j, j=1, 2, . . . C, where C is the total number of clusters, and m_ijis the degree of membership of the i-th pattern to the j-th cluster. In addition, the solution must satisfy the constraints that the membership value of each pattern in any given cluster must be less than or equal to one:
0≦m_ij≦1 (13)
and the sum of its membership values over all clusters must be equal to 1:

[0093]

\begin{matrix} \sum_{j = 1}^{C} m_{ij} = 1 & (14) \end{matrix}

[0094] In an embodiment of the invention, the squared distance d²(x_i, c_j) is the Euclidean distance between the i-th point in Rⁿand the j-th reference point. Equations 13 and 14 ensure that the solutions to Eq. 6 represent true fuzzy partitions of the data set among all the specified classes. In the above equation, q∈[1∞) is a weighting exponent known as the “fuzziness index” or “fuzzifier” that controls the degree of fuzziness of the resulting clusters. For q=1 the partitions are crisp, and as q→∞ the clusters become increasingly fuzzy.

[0095] The determination of reference points c_j, j=1,2, . . . , C using FCM is illustrated in FIG. 4, according to an embodiment of the invention. The process starts with step 405. In step 410, an iteration counter p is initialized. In step 415, an initial choice for the cluster centroids {c_j, j=1,2, . . . , C} is made. Given this choice for {c_j}, in step 420 the degree of membership of each point x_iin each cluster is calculated using the following formula:

[0096]

\begin{matrix} m_{ij} = \frac{{[\frac{1}{d^{2} (x_{i}, c_{j})}]}^{\frac{1}{q - 1}}}{\sum_{k = 1}^{C} {[\frac{1}{d^{2} (x_{i}, c_{k})}]}^{\frac{1}{q - 1}}} & (15) \end{matrix}

In step 425, the objective function J_q^pis evaluated using Eq. 16:

[0097]

\begin{matrix} J_{q}^{p} = \sum_{j = 1}^{C} \sum_{i = 1}^{N} m_{ij}^{q} d^{2} (x_{i}, c_{j}) & (16) \end{matrix}

In step 430, new centroids c_jare computed using the formula:

[0098]

\begin{matrix} c_{j} = \frac{\sum_{i = 1}^{N} m_{ij}^{q} x_{i}}{\sum_{i = 1}^{N} m_{ij}^{q}} & (17) \end{matrix}

In step 435, m_ijare recalculated using the new centroids and Eq. 15. In step 440, the iteration counter p is incremented. In step 445, J_q^pis recalculated in light of the new m_ijdetermined in step 435.

[0099] In step 450, the difference between J_q^pand its predecessor value J_q^p−1is determined. If the difference is sufficiently small, as indicated in the inequality |J_q¹−J_q⁰|>ε, where ε is a small positive constant (here ε=0.0009), then the process concludes at step 455, and the most recently determined {c_j} is used as the set of reference points for partitioning purposes. Otherwise, another set of centroids is determined in step 430. The process will continue until the condition of step 450 is satisfied.

[0100] Once the convergence criterion in step 450 has been met, the new centroids computed by Eq. 17 are used to partition the input data set into a set of Voronoi cells. Such cells are illustrated in FIG. 5. A set 500 is shown partitioned into Voronoi cells, such as cells 505A through 505C. The Voronoi cells include centroids 510A through 510C respectively.

[0101] Once all the local networks are trained, additional patterns from the input set of patterns can be mapped into R^mas illustrated in FIG.6. The process begins with step 605. In step 610, the distance of the input pattern x to each reference point in {c_i, i=1,2, . . . c; c_i∈Rⁿ} is determined. In step 615, the point c_jthat is nearest to the input pattern x_is identified. In step 620, the pattern x is mapped to a point y in R^m, x→y, x∈Rⁿ, y∈R^musing the local neural network Net_j^Lassociated with the reference point c_jidentified in step 615. The process concludes with step 625.

[0102] Note that new patterns in Rⁿthat not in the original input set can also be projected into R^min the manner shown in FIG. 6. Once the system is trained, new patterns in Rⁿare mapped by identifying the nearest local network and using that network in a feed-forward manner to perform the projection. An embodiment of a system that does this is illustrated in FIG. 7. The input for the system is a pattern 705 in Rⁿ. This point is defined by its n attributes, (x₁, x₂, . . . x_n). The system includes a dispatcher module 710, which compares the distance of the input point to the network centers (i.e., the reference points), and forwards the input point to one of the available local neural networks 701, 702, or 703. Specifically, the input pattern is sent to the local neural network associated with the reference point nearest to the input pattern. The chosen network then performs the final projection, resulting in an output point in R^m.

[0103] C. Local Nonlinear Mapping Networks—Algorithm III

[0104] The ability of a single network to reproduce the general structure of the nonlinear map suggests an alternative embodiment to overcome some of the complexities of clustering in higher dimensions. Conceptually, the alternative embodiment differs from Algorithm II in the way it partitions the data space. In contrast to the previous method, this process partitions the output space, and clusters the training patterns based on their proximity on the m-dimensional nonlinear map rather than their proximity in the n-dimensional input space. For the training set, the assignment to a partition is straightforward. The images of the points in the training set on the nonlinear map are derived directly from the iterative algorithm described in Section II. For new points that are not part of the training set, the assignment is based on approximate positions derived from a global neural network trained with the entire training set, like the one described in section II. A. The general flow of the algorithm is similar to the one described in section II. B.

[0105] The training phase for this embodiment is illustrated in FIG. 8. The method begins at step 805. In step 810, a random set of patterns {x_i, i=1,2, . . . , k; x_i∈Rⁿ} is extracted from the input data set. In step 815, the patterns x_iare mapped from Rⁿto R^musing the iterative nonlinear mapping algorithm described in section I B (x_i→y_{i, i=}1,2, . . . , k, x_i∈Rⁿ, y_{i ∈R}^m). This mapping serves to define a training set T of ordered pairs (x_i, y_i), T={(x_i, y_i), i=1,2, . . . , K}.

[0106] In step 820, the points {y_{i, i=}1,2, . . . , k, y_i∈R^m} are clustered into c clusters associated with c points in R^m, {c_i, i=1,2, . . . c; c,E∈R^m}. In the illustrated embodiment, fuzzy clusters are formed in this step using the FCM algorithm of FIG. 4. In step 825, the training set T is partitioned into c disjoint clusters C_jbased on the distance of the images y_ifrom the cluster prototypes, {C_j,={(x_i, y_i): d(y_i, c_j)≦d(y_i, c_k) for all k≠j; j=1,2, . . . , c; i=1,2, . . . , k}}. In step 830, c independent local neural networks {Net_i^L, i=1,2, . . . , c} are trained with the respective clusters C_jderived in step 825. In step 835, a global network Net^Gis trained with the entire training set T. The process concludes with step 840.

[0107] Once all the networks are trained, remaining input patterns from the input data set and any new patterns in Rⁿare projected using a tandem approach. An embodiment of this is illustrated in FIG. 9. The projection process begins at step 905. In step 910, each input pattern x to be projected into R^mis mapped, x→y′, x∈Rⁿ, y′ ∈R^m, using the global network Net^Gderived in step 835.

[0108] In step 915, the distance from y′ to each reference point c_iin {c_i, i=1,2, . . . c; c_i∈R^m} is determined. In step 920, the point c_jclosest to y′ is determined. In step 925, x is mapped into R^m, x→y, using the local neural network associated with c_j, Net_j^L. The process ends with step 930.

[0109] A system for performing the overall mapping x→y is shown in FIG. 10. First, an input pattern 1005 ∈Rⁿis projected by the global network 1010, Net^G, to obtain point 1012 (y′) ∈R^m. Point y′ can be viewed as having approximate coordinates on the nonlinear map. These coordinates are used to identify the nearest local network 1021 (Net_j^L) from among the possible local neural networks 1021 through 1023, based on the proximity of y′ to each c_i. Input point 1005 is projected once again, this time by the nearest local network 1021 to produce the final image 1030 on the display map.

III. Environment

[0110] The present invention may be implemented using hardware, software or a combination thereof and may be implemented in a computer system or other processing system. An example of such a computer system 1100 is shown in FIG. 11. The computer system 1000 includes one or more processors, such as processor 1104. The processor 1104 is connected to a communication infrastructure 1106 (e.g., a bus or network). Various software embodiments can be described in terms of this exemplary computer system. After reading this description, it will become apparent to a person skilled in the relevant art how to implement the invention using other computer systems and/or computer architectures.

[0111] Computer system 1100 also includes a main memory 1108, preferably random access memory (RAM), and may also include a secondary memory 1110. The secondary memory 1110 may include, for example, a hard disk drive 1112 and/or a removable storage drive 1114, representing a floppy disk drive, a magnetic tape drive, an optical disk drive, etc. The removable storage drive 1114 reads from and/or writes to a removable storage unit 1118 in a well known manner. Removable storage unit 1118 represents a floppy disk, magnetic tape, optical disk, etc. As will be appreciated, the removable storage unit 1118 includes a computer usable storage medium having stored therein computer software and/or data. In an embodiment of the invention, removable storage unit 1118 can contain input data to be projected.

[0112] Secondary memory 1110 can also include other similar means for allowing computer programs or input data to be loaded into computer system 1100. Such means may include, for example, a removable storage unit 1122 and an interface 1120. Examples of such may include a program cartridge and cartridge interface (such as that found in video game devices), a removable memory chip (such as an EPROM, or PROM) and associated socket, and other removable storage units 1122 and interfaces 1120 which allow software and data to be transferred from the removable storage unit 1122 to computer system 1100.

[0113] Computer system 1100 may also include a communications interface 1124. Communications interface 1124 allows software and data to be transferred between computer system 1100 and external devices. Examples of communications interface 1124 may include a modem, a network interface (such as an Ethernet card), a communications port, a PCMCIA slot and card, etc. Software and data transferred via communications interface 1124 are in the form of signals 1128 which may be electronic, electromagnetic, optical or other signals capable of being received by communications interface 1124. These signals 1128 are provided to communications interface 1124 via a communications path (i.e., channel) 1126. This channel 1126 carries signals 1128 and may be implemented using wire or cable, fiber optics, a phone line, a cellular phone link, an RF link and other communications channels. In an embodiment of the invention, signals 1128 can include input data to be projected.

[0114] In this document, the terms “computer program medium” and “computer usable medium” are used to generally refer to media such as removable storage drive 1114, a hard disk installed in hard disk drive 1112, and signals 1128. These computer program products are means for providing software to computer system 1100. The invention is directed to such computer program products.

[0115] Computer programs (also called computer control logic) are stored in main memory 1108 and/or secondary memory 1110. Computer programs may also be received via communications interface 1124. Such computer programs, when executed, enable the computer system 1100 to perform the features of the present invention as discussed herein. In particular, the computer programs, when executed, enable the processor 1104 to perform the features of the present invention. Accordingly, such computer programs represent controllers of the computer system 1100.

[0116] In an embodiment where the invention is implemented using software, the software for performing the training and projection phases of the invention may be stored in a computer program product and loaded into computer system 1100 using removable storage drive 1114, hard drive 1112 or communications interface 1124.

[0117] In another embodiment, the invention is implemented using a combination of both hardware and software.

VI. Conclusion

[0118] While various embodiments of the present invention have been described above, it should be understood that they have been presented by way of example, and not limitation. It will be apparent to persons skilled in the relevant art that various changes in detail can be made therein without departing from the spirit and scope of the invention. Thus the present invention should not be limited by any of the above described exemplary embodiments, but should be defined only in accordance with the following claims and their equivalents.

Claims

What is claimed is:

1. A method of mapping a set of n-dimensional input patterns to an m-dimensional space for display of said patterns using locally defined neural networks, comprising the steps of:

(a) creating a set of locally defined neural networks trained according to a mapping of a subset of the n-dimensional input patterns into an m-dimensional output space; and

(b) mapping additional n-dimensional input patterns using the locally defined neural networks wherein step (a) comprises the steps of:

(i) selecting k patterns from the subset of n-dimensional input patterns, {x_i, i=1, 2, . . . k, x_i∈Rⁿ};

(ii) mapping the patterns {x_i} into an m-dimensional space (x_i→y_i, i=1, 2, . . . k, y_i∈R^m), to form a training set T={(x_i, y_i), i=1, 2, . . . k};

(iii) determining c n-dimensional reference points, {(c_i; i=1, 2, . . . c, c_i∈Rⁿ};

(iv) partitioning T into c disjoint clusters C_jbased on a distance function d, {C_j={(x_i, y_i): d(x_i, y_i)≦d(x_i, c_k) for all k≠j; j=1, 2, . . . c; i=1, 2, . . . k}; and

(v) training c independent local networks {Net_i^L, i=1, 2, . . . c}, with respective pattern subsets C_i.

2. The method of claim 1, wherein said step (iii) is performed using a clustering methodology.

3. The method of claim 1, wherein said step (b) comprises the steps of:

(i) for an additional n-dimensional input pattern x∈Rⁿ, determining the distance to each reference point in {c_i};

(ii) identifying a reference point c_jclosest to the input pattern x; and

(iii) mapping x→y, y∈R^m, using the local neural network Net_i^Lassociated with the reference point c_jidentified in step (ii).

4. A method of mapping a set of n-dimensional input patterns to an m-dimensional space for display of said patterns using locally defined neural networks, comprising the steps of:

(a) creating a set of locally defined neural networks trained according to a mapping of a subset of the n-dimensional input patterns into an m-dimensional output space; and

(b) mapping additional n-dimensional input patterns using the locally defined neural networks wherein step (a) comprises the steps of:

(i) selecting k patterns of the set of n-dimensional input patterns, {x_i, i=1, 2, . . . k, x_i∈Rⁿ};

(ii) mapping the patterns {x_i} into an m-dimensional space, (x_i→y_i, i=1, 2, . . . k, y_i∈R^m), to form a training set T={(x_i, y_i), i=1, 2, . . . k};

(iii) determining c m-dimensional reference points, {c_i, i=1, 2, . . . c, c_i∈R^m};

(iv) partitioning T into c disjoint clusters C_jbased on a distance function d, {C_j={(x_i, y_i): d(y_i, c_j)≦d(y_i, c_k) for all k≠j, j=1, 2, . . . c; i=1, 2, . . . k)};

(v) training c independent local networks {Net_i^L, i=1, 2, . . . c}, with respective pattern subsets C_i; and

(vi) training a global network Net^Gusing all the patterns in T.

5. The method of claim 4, wherein said step (iii) is performed using a clustering methodology.

6. The method of claim 4, wherein step (b) comprises the steps of:

(i) for an additional n-dimensional pattern x∈Rⁿ, mapping x→y′, y′∈R^m, using Net^G;

(ii) determining the distance of y′ to each reference point in {c_i};

(iii) identifying a reference point c_jclosest to y′; and

(iv) mapping x→y, y∈R^m, using the local neural network Net_j^Lassociated with the reference point c_jidentified in step (iii).

7. A computer program product comprising a computer usable medium having computer readable program code means embodied in said medium for causing an application program to execute on a computer that maps a set of n-dimensional input patterns to an m-dimensional space for display of said patterns using locally defined neural networks, said computer readable program code means comprising:

a first computer readable program code means for causing the computer to create a set of locally defined neural networks trained according to a mapping of a subset of the n-dimensional input patterns into an m-dimensional space; and

a second computer readable program code means for causing the computer to project additional n-dimensional patterns of the input set using the locally defined neural networks;

wherein said first computer readable code means comprises:

(i) computer readable program code means for selecting k patterns from the subset of n-dimensional input patterns, {x_i, i=1, 2, . . . k, x_i∈Rⁿ};

(ii) computer readable program code means for mapping the patterns {x_i} into an m-dimensional space (x_i→y_i, i=1, 2, . . . k, y_i∈R^m), to form a training set T={(x_i, y_i), i=1, 2, . . . k};

(iii) computer readable program code means for determining c n-dimensional reference points, {c_i, i=1, 2, . . . c, c_i∈Rⁿ};

(iv) computer readable program code means for partitioning T into c disjoint clusters C_jbased on a distance function d, {C_j={(x_i, y_i): d(x_i, y_i)≦d(x_i, c_k) for all k ≠j; j=1, 2, . . . c; i=1, 2, . . . k}; and

(v) computer readable program code means for training c independent local networks {Net_i^L, i=1, 2, . . . c}, with respective pattern subsets C_i.

8. The computer program product of claim 7, wherein said first computer readable program code means uses a clustering methodology.

9. The computer program product of claim of claim 7, wherein said second computer readable code means comprises:

(i) for an additional n-dimensional input pattern x∈Rⁿ, computer readable code means for determining the distance to each reference point in {c_i};

(ii) computer readable program code means for identifying a reference point c_jclosest to the input pattern x; and

(iii) computer readable program code means for mapping x→y, y∈R^m, using the local neural network Net_i^Lassociated with the reference point c_jidentified in step (ii).

10. A computer program product comprising a computer usable medium having computer readable program code means embodied in said medium for causing an application program to execute on a computer that maps a set of n-dimensional input patterns to an m-dimensional space for display of said patterns using locally defined neural networks, said computer readable program code means comprising:

a second computer readable program code means for causing the computer to project additional n-dimensional patterns of the input set using the locally defined neural networks; wherein said first computer readable program code means comprises:

(i) computer readable program code means for selecting k patterns of the set of n-dimensional input patterns, {x_i, i=1, 2, . . . k, x_i∈Rⁿ};

(ii) computer readable program code means for mapping the patterns {x_i} into an m-dimensional space, (x_i→y_i, i=1, 2, . . . k, y_i∈R^m), to form a training set T={(x_i, y_i), i=1, 2, . . . k};

(iii) computer readable program code means for determining c m-dimensional reference points, {c_i, i=1, 2, . . . c, c_i∈R^m};

(iv) computer readable program code means for partitioning T into c disjoint clusters C_jbased on a distance function d, {C_j={(x_i, y_i): d(y_i, c_j)≦d(y_i, c_k) for all k≠j; j=1, 2, . . . c; i=1, 2, . . . k)};

(v) computer readable program code means for training c independent local networks {Net_i^L, i=1, 2, . . . c}, with respective pattern subsets C_i; and

(vi) computer readable program code means for training a global network Net^Gusing all the patterns in T.

11. The computer program product of claim 10, wherein said first computer readable program code means uses a clustering methodology.

12. The computer program product of claim 10, wherein said second computer readable program code means comprises:

(i) for an additional n-dimensional pattern x∈Rⁿ, computer readable program code means for mapping x→y′, y′∈R^m, using Net^G;

(ii) computer readable program code means for determining the distance of y′ to each reference point in {c_i};

(iii) computer readable program code means for identifying a reference point c_jclosest to y′; and

(iv) computer readable program code means for mapping x→y, y∈R^m, using the local neural network Net_j^Lassociated with the reference point c_jidentified in step (iii).

Patent Citations (82)

Patent	Date	Inventor	Cited By
US4773099(A)	1988-09-01	Bokser	Applicant
US4811217(A)	1989-03-01	Tokizane et al.	Applicant
US4859736(A)	1989-08-01	Rink	Applicant
US4908773(A)	1990-03-01	Pantoliano et al.	Applicant
US4935875(A)	1990-06-01	Shah et al.	Applicant
US4939666(A)	1990-07-01	Hardman	Applicant
US5010175(A)	1991-04-01	Rutter et al.	Applicant
US5025388(A)	1991-06-01	Cramer, III et al.	Applicant
US5095443(A)	1992-03-01	Watanabe	Applicant
US5155801(A)	1992-10-01	Lincoln	Applicant
US5167009(A)	1992-11-01	Skeirik	Applicant
US5181259(A)	1993-01-01	Rorvig	Applicant
US5240680(A)	1993-08-01	Zuckermann et al.	Applicant
US5260882(A)	1993-11-01	Blanco et al.	Applicant
US5265030(A)	1993-11-01	Skolnick et al.	Applicant
US5270170(A)	1993-12-01	Schatz et al.	Applicant
US5276771(A)	1994-01-01	Manukian et al.	Examiner
US5288514(A)	1994-02-01	Ellman	Applicant
US5307287(A)	1994-04-01	Cramer, III et al.	Applicant
US5323471(A)	1994-06-01	Hayashi	Applicant
US5331573(A)	1994-07-01	Balaji et al.	Applicant
US5434796(A)	1995-07-01	Weininger	Applicant
US5436850(A)	1995-07-01	Eisenberg et al.	Applicant
US5442122(A)	1995-08-01	Noda et al.	Applicant
US5461697(A)	1995-10-01	Nishimura et al.	Examiner
US5463564(A)	1995-10-01	Agrafiotis et al.	Applicant
US5499193(A)	1996-03-01	Sugawara et al.	Applicant
US5519635(A)	1996-05-01	Miyake et al.	Applicant
US5524065(A)	1996-06-01	Yagasaki	Applicant
US5526281(A)	1996-06-01	Chapman et al.	Applicant
US5545568(A)	1996-08-01	Ellman	Applicant
US5549974(A)	1996-08-01	Holmes	Applicant
US5553225(A)	1996-09-01	Perry	Applicant
US5565325(A)	1996-10-01	Blake	Applicant
US5574656(A)	1996-11-01	Agrafiotis et al.	Applicant
US5585277(A)	1996-12-01	Bowie et al.	Applicant
US5602755(A)	1997-02-01	Ashe et al.	Applicant
US5602938(A)	1997-02-01	Akiyama et al.	Applicant
US5612895(A)	1997-03-01	Balaji et al.	Applicant
US5621861(A)	1997-04-01	Hayashi et al.	Applicant
US5634017(A)	1997-05-01	Mohanty et al.	Applicant
US5635598(A)	1997-06-01	Lebl et al.	Applicant
US5670326(A)	1997-09-01	Beutel	Applicant
US5679582(A)	1997-10-01	Bowie et al.	Applicant
US5684711(A)	1997-11-01	Agrafiotis et al.	Applicant
US5703792(A)	1997-12-01	Chapman	Applicant
US5712171(A)	1998-01-01	Zambias et al.	Applicant
US5712564(A)	1998-01-01	Hayosh	Applicant
US5729662(A)	1998-03-01	Rozmus	Examiner
US5734796(A)	1998-03-01	Pao	Examiner
US5736412(A)	1998-04-01	Zambias et al.	Applicant
US5740326(A)	1998-04-01	Boulet et al.	Applicant
US5789160(A)	1998-08-01	Eaton et al.	Applicant
US5807754(A)	1998-09-01	Zambias et al.	Applicant
US5811241(A)	1998-09-01	Goodfellow et al.	Applicant
US5832494(A)	1998-11-01	Egger et al.	Applicant
US5858660(A)	1999-01-01	Eaton et al.	Applicant
US5861532(A)	1999-01-01	Brown et al.	Applicant
US5866334(A)	1999-02-01	Beutel	Applicant
US5901069(A)	1999-05-01	Agrafiotis et al.	Applicant
US5908960(A)	1999-06-01	Newlander	Applicant
US5933819(A)	1999-08-01	Skolnick et al.	Applicant
US6014661(A)	2000-01-01	Ahlberg et al.	Applicant
US6037135(A)	2000-03-01	Kubo et al.	Applicant
US6049797(A)	2000-04-01	Guha et al.	Applicant
US6134537(A)	2000-10-01	Pao et al.	Examiner
US6185506(B1)	2001-02-01	Cramer et al.	Applicant
US6192351(B1)	2001-02-01	Persaud	Examiner
EP355266(B1)	1990-02-01		Applicant
EP355628(B1)	1990-02-01		Applicant
EP770876(A1)	1997-05-01		Applicant
EP818744(A2)	1998-01-01		Applicant
WO91/19735	1991-12-01		Applicant
WO92/00091	1992-01-01		Applicant
WO93/20242	1993-10-01		Applicant
WO94/28504	1994-12-01		Applicant
WO95/01606	1995-01-01		Applicant
WO97/09342	1997-03-01		Applicant
WO97/20952	1997-06-01		Applicant
WO97/27559	1997-07-01		Applicant
WO98/20437	1998-05-01		Applicant
WO98/20459	1998-05-01		Applicant

Non-Patent Literature (180)

Borg, Ingwer and Groenen, Patrick, Modern Multidimensional Scaling Theory and Applications, Springer Series in Statistics, 1997, entire book submitted.Applicant
Agrafiotis, D.K. et al., “Advances in diversity profiling and combinatorial series design,” Molecular Diversity, Kluwer Academic Publishers, vol. 4, 1999, pp. 1-22.Applicant
Agrafiotis, D.K. and Lobanov, V.S., “An Efficient Implementation of Distance-Based Diversity Measures Based on k-d Trees,” J. Chem. Inf. Comput. Sci., American Chemical Society, vol. 39, No. 1, Jan./Feb. 1999, pp. 51-58.Applicant
Agrafiotis, D.K. and Lobanov, V.S., “Bridging The Gap Between Diversity And QSAR,” Abstracts of Papers Part 1: 215th ACS National Meeting, Mar. 29-Apr. 2, 1998, p. 181-COMP.Applicant
Agrafiotis, D.K. and Jaeger, E.P., “Directed Diversity®: An Operating System For Combinatorial Chemistry,” Abstracts of Papers Part 1: 211th ACS National Meeting, Mar. 24-28, 1996, p. 46-COMP.Applicant
Agrafiotis, D.K., “Diversity of Chemical Libraries,” Encyclopedia of Computational Chemistry, John Wiley & Sons Ltd, vol. 1:A-D, 1998, pp. 742-761.Applicant
Agrafiotis, D.K., “On the Use of Information Theory for Assessing Molecular Diversity,” Journal of Chemistry Information and Computer Sciences, American Chemical Society, vol. 37, No. 3, May/Jun. 1997, pp. 576-580.Applicant
Agrafiotis, D.K. et al., “Parallel QSAR”, Abstracts of Papers Part 1: 217th ACS National Meeting, Mar. 21-25, 1999, p. 50-COMP.Applicant
Agrafiotis, D.K. et al., “PRODEN: A New Program for Calculating Integrated Projected Populations,” Journal of Computational Chemistry, John Wiley & sons, Inc., vol. 11, No. 9, Oct. 1990, pp. 1101-1110.Applicant
Agrafiotis, D.K. and Jaeger, E.P., “Stochastic Algorithms for Exploring Molecular Diversity.” Abstracts of Papers Part 1: 213th ACS National Meeting, APr. 13-17, 1997, p. 16-CINF.Applicant
Agrafiotis, D., “Theoretical Aspects of the Complex: Arts and New Technologies,” Applications and Impacts Information Processing '94, North-Holland, vol. II, 1994, pp. 714-719.Applicant
Biswas, G. et al., “Evaluation of Projection Algorithms,” IEEE Transactions On Pattern Analysis And Machine Intelligence, IEEE Computer Society, vol. PAMI-3, No. 6, Nov. 1981, pp. 701-708.Applicant
Bonchev, D. and Trinajstić, N., “Information theory, distance matrix, and molecular branching,” The Journal of Chemical Physics, American Institute of Physics, vol. 67, No. 10, Nov. 15, 1977, pp. 4517-4533.Applicant
Chang, C.L. and Lee, R.C.T., “A Heuristic Relaxation Method for Nonlinear Mapping in Cluster Analysis,” IEEE Transactions on Systems, Man, and Cybernetics, IEEE Systems, MAn, and Cybernetics Society, vol. SMC-3, Mar. 1973, pp. 197-200.Applicant
Cramer, R.D. et al., “Virtual Compound Libraries: A New Approach to Decision Making in Molecular Discovery Research,” Journal of Chemical Information and Computer Science, American Chemical Society, vol. 38, No. 6, Nov./Dec. 1998, pp. 1010-1023.Applicant
DeMers, D. and Cottrell, G., “Non-Linear Dimensionality Reduction,” Advances in Neural Information Processing Systems, vol. 5, 1993, pp. 580-587.Applicant
Frey, P.W. and Slate, D.J., “Letter Recognition Using Holland-Style Adaptive Classifiers,” Machine Learning, Kluwer Academic Publishers, vol. 6, 1991, pp. 161-182.Applicant
Friedman, J.H., “Exploratory Projection Pursuit,” Journal of the American Statistical Association, American Statistical Association, vol. 82, No. 397, Mar. 1987, pp. 249-266.Applicant
Friedman J.H. and Turkey, J.W., “A Projection Pursuit Algorithm for Exploratory Data Analysis,” IEEE Transactions on Computers, IEEE Computer Society, vol. C-23, No. 9, Sep. 1974, pp. 881-889.Applicant
Garrido, L. et al., “Use of Multilayer Feedforward Neural Nets As A Display Method for Multidimensional Distributions,” International Journal of Neural Systems, World Scientific Publishing Co. Pte. Ltd., vol. 6, No. 3, Sep. 1995, pp. 273-282.Applicant
Ghose, A.K. et al., “Prediction of Hydrophobic (Lipophilic) Properties of Small Organic Molecules Using Fragmental Methods: An Analysis of ALOGP and CLOGP Methods,” Journal of Physical Chemistry, American Chemical Society, vol. 102, No. 21, Mat 21, 1998, pp. 3762-3772.Applicant
Hall, L.H. and Kier, L.B., “The Molecular Connectivity Chi Indexes and Kappa Shape Indexes in Structure- Property Modeling,” Reviews in Computational Chemistry: Advances, VCH Publishers, Inc., 1991, pp. 367-422.Applicant
Hecht-Nielsen, R., “Replicator Neural Networks for Universal Optimal Source Coding,” Science, American Association for the Advancement of Science, vol. 269, Sep. 29, 1995, pp. 1860-1863.Applicant
Hotelling, H., “Analysis of a Complex of Statistical Variables into Principal Components,” The Journal of Educational Phsychology, Warwick and York, Inc., vol. XXIV, No. 6, Sep. 1933, pp. 417-441.Applicant
Hotelling, H., “Analysis of a Complex of Statistical Variables into Principal Components,” The Journal of Educational Psychology, Warwick and York, Inc., vol. XXIV, No. 7, Oct. 1933, pp. 498-520.Applicant
Lee, R.C.T. et al., “A Triangulation MEthod for the Sequential Mapping of Points from N-Space to Two-Space,” IEEE Transactions on Computers, The Institute of Electrical and Electronics Engineers, Mar. 1977, pp. 288-292.Applicant
Lipinski, C.A. et al., “Experimental and computational approaches to estimate solubility and permeability in drug discovery and development settings,” Advanced Drug Delivery Reviews, Elsevier Science B.V., vol. 23, 1997, pp. 3-25.Applicant
Lobanov, V.S. and Agrafiotis, D.K., “Intelligent Database Mining Techniques,” Abstracts of Papers Part 1: 215th ACS National Meeting, Mar. 29-Apr. 2, 1998, p. 19-COMP.Applicant
Lobanov, V.S. et al., “National Selections from Virtual Libraries,” Abstracts of Papers Part 1: 217th ACS National Meeting, Mar. 21-25, 1999, p. 181-COMP.Applicant
Mao, J. and Jain, A.K., “Artificial Neural Networks for Feature Extraction and Multivariate Data Projection,” IEEE transactions on Neural Networks, IEEE Neural Networks, vol. 6, No. 2, Mar. 1995, pp. 296-317.Applicant
Oja, E., “Principal Components, Minor Components, and Linear Neural Networks,” Neural Networks, Pergamon Press Ltd., vol. 5, 1992, pp. 927-935.Applicant
Patterson, D.E. et al., “Neighborhood Behavior: A Useful Concept for Validation of ‘Molecular Diversity’ Descriptors,” Journal of Medicinal Chemistry, American Chemical Society, vol. 39, No. 16, 1996, pp. 3049-3059.Applicant
Lykett, C.E., “Imrpoving the Efficiency of Sammon's Nonlinear Mapping by Using Clustering Archetypes,” Electronics Letters, The Institute of Electrical Engineers, vol. 14, No. 25, Dec. 7, 1978, pp. 799-800.Applicant
Rubner, J. and Tavan, P., “A Self-Organizing Network for Principal-Component Analysis,” Europhysics Letters, European Physical Society, vol. 10, No. 7, Dec. 1, 1989, pp. 693-698.Applicant
Sadowski, J. et al., “Assessing Similarity and Diversity of Combinatorial Libraries by Spatial Autocorrelation Functions and Neural Networks,” Angewandte Chemie, VCH, vol. 34, No .23/24, Jan. 5, 1996, pp. 2674-2677.Applicant
Thompson, L.A. and Ellman, J.A., “Synthesis and Applications of Small Molecule Libraries,” Chemical Reviews, American Chemical Society, vol. 96, No. 1, Jan./Feb. 1996, pp. 555-600.Applicant
Barnard, John M. and Downs, Geoff M., “Computer representation and manipulation of combinatorial libraries,” Perspectives in Drug Discovery and Design, Kluwer Academic Publishers, 1997, pp. 13-30.Applicant
Brint, Andrew T. and Willett, Peter, “Upperbound procedures for the identification of similar three-dimensional chemical structures,” Journal of Computer-Aided Molecular Design, ESCOM Science Publishers B.V., vol. 2, No. 4, Jan. 1989, pp. 311-320.Applicant
Brown, Robert D. and Martin, Yvonne C., “Designing Combinatorial Library Mixtures Using a Genetic Algorithm,” Journal of Medicinal Chemistry, American Chemical Society, vol. 40, No. 15, 1997, pp. 2304-2313.Applicant
Gillet, Valerie J. et al., “The Effectiveness of Reactant Pools for Generating Structurally-Diverse Combinatorial Libraries,” Journal of Chemical Information Computer Sciences, American Chemical Society, vol. 37, No. 4, 1997, pp. 731-740.Applicant
Gillet, Valerie J. et al., “Selecting Combinatorial Libraries to Optimize Diversity and Physical Properties,” Journal of Chemical Information Computer Sciences, American Chemical Society, vol. 39, No. 1, 1999, pp. 169-177.Applicant
Kearsley, Simon K. et al., “Chemical Similarity Using Physiochemical Property Descriptors,” Journal of Chemical Information Computer Science, American Chemical Society, vol. 36, No .1 , 1996, pp. 118-127.Applicant
Leland, Burton A. et al., “Managing the Combinatorial Explosion,” Journal of Chemical Information Computer Science, American Chemical Society, vol. 37, No. 1, 1997, pp. 62-70.Applicant
Lewis, Richard A. et al., “Similarity Measures for Rational Set Selection and Analysis of Combinatorial Libraries: The Diverse Property-Derived (DPD) Approach,” Journal of Chemical Information Computer Sciences, American Chemical Society, vol. 37, No. 3, 1997, pp. 599-614.Applicant
Martin, Eric J. and Critchlow, Roger E., “Beyond Mere Diversity: Tailoring Combinatorial Libraries for Drug Discovery,” Journal of Combinatorial Chemistry, American Chemical Society, vol. 1, No. 1, 1999, pp. 32-45.Applicant
Sheridan, Robert P. et al., “Chemical Similarity Using Geometric Atom Pair Descriptors,” Journal of Chemical Information Computer Sciences, Americna Chemical Society, vol. 36, no. 1, 1996, pp. 128-136.Applicant
Willett, Peter et al., “Chemical Similarity Searching,” Journal of Chemical Information Computer Sciences, Americna Chemical Society, vol. 38, No. 6, 1998, pp. 983-996.Applicant
Agrafiotis, Dimitris K. and Lobanov, Victor S., “Ultrafast Algorithm for Designing Focused Combinational Arrays,” J. Chem. Inf. Comput. Sci., American Chemical Society, 2000, vol. 40, No. 4, pp. 1030-1038.Applicant
Ajay et al., “Can We Learn To Distinguish between ‘Drug-Like’ Molecules?” Journal of Medicinal Chemistry, 1998, American Chemical Society, vol. 41, No. 18, pp. 3314-3324.Applicant
English-language Abstract of European Patent No. 0 355 628, printed from Dialog File No. 351(Feb., 1990—Date of publication of application).Applicant
Brown, Robert D. and Martin, Yvonne C., “the Information Content of 2D and 3D Structural Descriptors Relevant to Ligand-Receptor Binding,” Journal of Chemical Information and Computer Sciences, American Chemical Society, 1997, vol. 37, No. 1, pp. 1-9.Applicant
Brown, Robert D. and Martin, Yvonne C., “Use of Structur-Activity Data To Compare Structure-Based Clustering Methods and Descriptors for Use in Compound Selection,” Journal of Chemical Information and Computer Sciences, American Chemical Society, 1996, vol. 36, No. 3, pp. 572-584.Applicant
Cummins, David J. et al., “Molecular Diversity in Chemical Databases: Comparison of Medicinal Chemistry Knowledge Bases and Databases of Commerically Available Compounds,” Journal of Chemical Information and Computer Sciences, American Chemical Society, 1996, vol. 36, No. 4, pp. 750-763.Applicant
Daylight Theory: Fingerprints (visited Sep. 26, 2000) <http://www.daylight.com/dayhtml/doc/theory/theory.finger.html>, 9 pages.Applicant
Daylight Theory: SMARTS (visited Sep. 26, 2000) <http://www.daylight.com/dayhtml/doc/theory/theory.smarts.html>, 10 pages.Applicant
Downs, Geoff M. and Barnard, John M., “Techniques for Generating Descriptive Fingerprints in Combinatorial Libraries,” J. Chem. Inf. Comput. Sci., American Chemical Society, 1997, vol. 37, No. 1, pp. 59-61.Applicant
Gillet, Valerie J., “Background Theory of Molecular Diversity,” Molecular Diversity in Drug Design, Kluwer Academic Publishers, 1999, pp. 43-65.Applicant
Good, Andrew C. and Lewis, Richard A., “New Methodology for Profiling Combinatorial Libraries and Screening Sets: Cleaning Up the Design Process with HARPick,” Journal of Medicinal Chemistry, American Chemical Society, 1997, vol. 40, No. 24, pp. 3926-3936.Applicant
Gorse, Dominique and Lahana, Roger, “Functional diversity of compund libraries,” Current opinion in chemical biology, Elsevier Science Ltd., Jun. 2000, vol. 4, No. 3, pp. 287-294.Applicant
Jamois, Eric A. et al., “Evaluation of Reagent-Based and Product-Based Strategies in the Design of Combinatorial Library Subsets,” Journal of Chemical Information and Computer Sciences, American Chemical Society, 2000, vol. 40, no. 1, pp. 63-70.Applicant
Leach, Andrew R. et al., “Implementation of a System for Reagent Selection and Library Enumeration, Profiling, and Design,” Journal of Chemical Information and Computer Sciences, American Chemical Society, 1999, vol. 39, No. 6, pp. 1161-1172.Applicant
Leach, Andrew R. and Hann, Michael M., “The in silico world of virtual libraries,” Drug discovery today, Elsevier Science Ltd., Aug. 2000, vol. 5, No. 8, pp. 326-336.Applicant
Lobanov, Victor S. and Agrafiotis, Dimitris K., “Stochastic Similarity Selections from Large Combinatorial Libraries,” Journal of Chemical Information and Computer Sciences, American Chemical Society, Mar./Arp. 2000, vol. 40, No. 2, pp. 460-470.Applicant
Matter, Hans and Pötter, Thorsten, “Comparing 3D Pharmacophore Triplets and 2D Fingerprints for Selecting Diverse Compound Subsets,” Journal of Chemical Information and Computer Sciences, American Chemical Society, 1999, vol. 39, No. 6, pp. 1211-1225.Applicant
Matter, Hans, “Selecting Optimally Diverse Compounds from Structure Databases: A Validation Study of Two-Dimensional and Three-Dimensional Molecular Descriptors,” Journal of Medicinal Chemistry, American Chemical Society, 1997, vol. 40, No. 8, pp. 1219-1229.Applicant
Sadowski, Jens and Kubinyi, Hugo, “A Scoring Scheme for Descriminating between Drugd and Nondrugs,” Journal of Medicinal Chemistry, American Chemical Society, 1998, vol. 41, No. 18, pp. 3325-3329.Applicant
Schnur, Dora, “Design and Diversity Analysis of Large Combinatorial Libraries Using Cell-Based Methods,” Journal of Chemical Information and Computer Sciences, American Chemical Society, 1999, vol. 39, No. 1, pp. 36-45.Applicant
Schuffenhauer, Ansgar et al., “Similarity Searching in Files of Three-Dimensional Chemical Structures: Analysis of the BIOSTER Database Using Two-Dimensional Fingerprints and Molecular Field Descriptors,” Journal of Chemical Information and Computer Sciences, American Chemical Society, 2000, vol. 40, No. 2, pp. 295-307.Applicant
Turner, David B. et al., “Rapid Quantification of Molecular Diversity for Selective Database Acquisition,” Journal of Chemical Information and Computer Sciences, American Chemical Society, 1997, vol. 37, No. 1, pp. 18-22.Applicant
Wang, Jing and Ramnarayan, Kal, “Toward Designing Drug-Like Libraries: A Novel Computational Approach for Prediction of Durg Feasability of Compounds,” Journal of Combinatorial Chemistry, American Chemical Society, Nov./Dec. 1999, vol. 1, No. 6, pp. 524-533.Applicant
Gasteiger, J. et al., “Assessment of the Diversity of Combinatorial Libraries by an Encoding of Molecular Surface Properties,” Abstracts of Papers Part 1: 211th ACS National Meeting, Mar. 24-28, 1996, p. 70-CINF.Applicant
Hassan, Moises et al., “Optimization and visualization of molecular diversity of combinatorial libraries,” Molecular Diversity, ESCOM Science Publishers B.V., 1996, vol. 2, pp. 64-74.Applicant
Bellman, R.E., Adaptive Control Processes: A Guided Tour, Princeton Univ. Press, Princeton, NJ (1961), entire book submitted.Applicant
Bezdek, J.C., Pattern Recognition with Fuzzy Objective Function Algorithms, Plenum Press, New York, NY (1981), entire book submitted.Applicant
Johnson, M.A., and Maggiora, G.M., Concepts and Applications of Molecular Similarity, John Wiley and Sons, New York, NY (1990), entire book submitted.Applicant
Kohonen, T., Self-Organizing Mapes, Springer-Verlag, Heidelberg, Germany (1995), entire book submitted.Applicant
Oja, E., Subspace Methods of Pattern Recognition, Research Studies Press, Letchworth, England, (1983), entire book submitted.Applicant
Agrafiotis, D.K., “A New Method For Analyzing Protein Sequence Relationships Based On Sammon Maps,” Protein Science, Cambridge University Press, vol. 6, No. 2, Feb. 1997, pp. 287-293.Applicant
Copy of International Search Report issued Oct. 18, 1999, for Appl. No. PCT/US99/09963, 7 pages.Applicant
Amzel, L.M., “Structure-based drug design,” Current Opinion in Biotechnology, vol. 9, No. 4, Aug. 1998, pp. 366-369.Applicant
Blaney, J.M. and Martin, E.J., “Computational approaches for combinatorial library design and molecular diversity analysis,” Current Opinion Chemical Biology, Current Biology Ltd., vol. 1, No. 1, Jun. 1997, pp. 54-59.Applicant
Brown, R.D. and Clark, D.E., “Genetic diveristy: applications of evolutionary algorithms to combinatorial library design,” Expert Opinion on Therapeutic Patents, vol. 8, No. 11, Nov. 1998, pp. 1447-1459.Applicant
Caflisch, A. and Karplus, M., “Computational combinatorial chemitry for de novo ligand design: Review and assessment,” Perspectives in Drug Discovery and Design, ESCOM Science Publishers B.V., vol. 3, 1995, pp. 51-84.Applicant
Danheiser, S.L., “Current Trends in Synthetic Peptide and Chemical Diversity Library Design,” Genetic Engineering News, May 1, 1994, pp. 10 and 31.Applicant
Eichler, U. et al., “Addressing the problem of molecular diversity,” Drugs of the Future, Prous Science, vol. 24, No. 2, 1999, pp. 177-190.Applicant
Felder, E.R. and Poppinger, D., “Combinatorial Compound Libraries for Enhanced Drug Discovery Approached,” Advances in Drug Research, Academic Press, vol. 30, 1997, pp. 112-199.Applicant
Geysen, H.M. and Mason, T.J., “Screening Chemically Synthesized PepTide Libraries for Biologically-Relevant Molecules,” Bioorganic & Medicinal Chemistry Letters, Pergamon Press, Ltd., vol. 3, No. 3, 1993, pp. 397-404.Applicant
Gobbi, A. et al., “New Leads By Selective Screening of Compounds From Large Databases,” Abstracts of Papers Part 1: 213th ACS National Meeting, Apr. 13-17, 1997, p. 67-CINF.Applicant
Houghten, R.A. et al., “The Use of Synthetic Peptide Combinatorial Libraries for the Identification of Bioactive Peptides,” Peptide Research, vol. 5 No. 6, 1992, pp. 351-358.Applicant
Klopman, G., “Artificial Intelligence Approach to Structure-Activity Studies. Computer Automated Structure Evaluation of Biological Activity of Organic Molecules,” Journal of the American Chemical Society, American Chemical Society, vol. 106, No. 24, Nov. 28, 1984, pp. 7315-7321.Applicant
Lajiness, M.S. et al., “Implementing Drug Screening Programs Using Molecular Similarity Methods,” QSAR: Quantitative Structure-Activity Relationships in Drug Design, Alan R. Liss, Inc., 1989, pp. 173-176.Applicant
Loew, G.H. et al., “Strategies for Indirect Computer-Aided Drug Design,” Pharmaceutical Research, Plenum Publishing Corporation, vol. 10, No. 4, 1993, pp. 475-486.Applicant
Lynch, M.F. et al., “Generic Structure Storage and Retrieval,” Journal of Chemical Information and Computer Sciences, American Chemical Society, vol. 25, No. 3, Aug. 1985, pp. 264-270.Applicant
Myers, P.L. et al., “Rapid, Reliable Drug Discovery,” Today's Chemist At Work, American Chemical Society, vol. 6, No. 7, Jul./Aug. 1997, pp. 46-48, 51 & 53.Applicant
Pabo, C.O. and Suchanek, E.G., “Computer-Aided Model-Building Strategies for Protein Design,” Biochemistry, American Chemical Society, vol. 25, No. 20, 1986, pp. 5987-5991.Applicant
Saudek, V. et al., “Solution Conformation of Endothelin-1 by H NMR, CD, and Molecular Modeling,” International Journal of Peptide Protein Res., Munksgaard International Publishers Ltd., vol. 37, No. 3, 1991, pp. 174-179.Applicant
Singh, J. et al., “Application of Genetic Algorithms to Combinatorial Synthesis: A Computational Approach to Lead Identification and Lead Optimization,” Journal of the American Chemical Society, American Chemical Society, vol. 118, No. 5, Feb. 7, 1996, pp. 1669-1676.Applicant
Van Drie, J.H. and Lajiness, M.S., “Approaches to virtual library design,” Drug Discovery today, Elsevier Science Ltd., vol. 3, No. 6, Jun. 1998, pp. 274-283.Applicant
Walters, W.P. et al., “Virtual screening—an overview,” Drug Discovery today, Elsevier Science Ltd., vol. 3, No. 4, Apr. 1998, pp. 160-178.Applicant
Weber, L., “Evolutionary combinatorial chemistry: application of genetic algorithms,” Drug Discovery today, Elsevier Science Ltd., vol. 3, No. 8, Au. 1998, pp. 379-385.Applicant
Weber, L. et al., “Optimization of the Biological Activity of Combinatorial Compound Libraries by a Genetic Algorithm,” Angewandte Chemie International Edition in English, VCH, vol. 34, No. 20, Nov. 3, 1995, pp. 2280-2282.Applicant
Graybill, T.L. et al., “Enhancing the Drug Discovery Process by Integration of High-Throughput Chemistry and Structure-Based Drug Design,” from Molecular Diversity and Combinatorial Chemistry: Libraries and Drug Discovery, Chaiken and Janda (eds.), American Chemical Society, 1996, pp. 16-27.Applicant
Saund, E., “Dimensionality-Reduction Using Connectionist Networks,” IEEE Transactions on Pattern Analysis and Machine Intelligence, IEEE, vol. 11, No. 3, Mar. 1989, pp. 304-314.Applicant
“3DP gains drug research patent”, Chemistry in Britain, The Royal Society of Chemistry, vol. 32, No. 1, Jan. 1996, p. 22.Applicant
“Accelerate the Discovery Cycle with Chem0XI”, Source and date of publication unclear, 2 pages.Applicant
Agrafiotis, D.K., “Stochastic Algorithms for Maximizing Molecular Diversity”, Journal of Chemical Information and Computer Sciences, American Chemical Society, vol. 37, No. 5, 1997, pp. 841-851.Applicant
Alsberg, B.K. et al., “Classification of pyrolysis mass spectra by fuzzy multivariate rule induction-comparison with regression, K-nearest neighbour, neural and decision-tree methods”, Analytica Chimica Acta, Elsevier Science B.V., vol. 348, No. 1-3, Aug. 20, 1997, pp. 389-407.Applicant
Andrea, T.A. and Kalayeh, H., “Applications of Neural Networks in Quantitative Structure-Activity Relationships of Dihydrofolate Reductase Inhibitors”, Journal of Medicinal Chemistry, American Chemical Society, vol. 34, No. 9, 1991, pp. 2824-2836.Applicant
Aoyama, T. et al., “Neural Networks Applied to Quantitative Structure-Activity Relationships Analysis”, Journal of Medicinal Chemistry, American Chemical Society, vol. 33, No. 9, 1990, pp. 2583-2590.Applicant
Aoyama, T. and Ichikawa, H., “Obtaining the Correlation Indices between Drug Activity and Structural Parameters Using a Neural Network”, Chemical & Pharmaceutical Bulletin, Pharmaceutical Society of Japan, vol. 39, No. 2, Feb. 1991, pp. 372-378.Applicant
“ArQule Inc”, from http://www.bioportfolio.com/arqule/products.htm, 5 pages, (Mar. 18, 1998).Applicant
Baum, R.M., “Combinatorial Approaches Provide Fresh Leads for Medicinal Chemistry”, Chemical 7 Engineering News, American Chemical Society, Feb. 7, 1994, pp. 20-26.Applicant
Bentley, J. L., “Multidimensional Binary Search Trees Used for Associative Searching”, Communications of the ACM, Association for Computing Machinery, Inc., vol. 18, No. 9, Sep. 1975, pp. 509-517.Applicant
Bottou, L. and Vapnik, V. “Local Learning Algorithms”, Neural Computation, Massachusetts Institute of Technology, vol. 4, No. 6, Nov. 1992, pp. 888-900.Applicant
Boulu, L.G. and Crippen, G.M., “Voronoi Binding Site Models: Calculation of Binding Modes and Influence of Drug Binding Data Accuracy”, Journal of Computational Chemistry, John Wiley & Sons, Inc., vol. 10, No. 5, Jul./Aug. 1989, pp. 673-682.Applicant
Boulu, L.G. et al., “Voronoi Binding Site Model of a Polycyclic Aromatic Hydrocarbon Binding Protein”, Journal of Medicinal Chemistry, American Chemical Society, vol. 33, No. 2, 1990, pp. 771-775.Applicant
Brown, R. D. and Martin, Y.C., “Use of Structure-Activity Data To Compare Structure-Based Clustering Methods and Descriptors for Use in Compound Selection”, Journal of Chemical Information and Computer Sciences, vol. 36, No. 3, 1996, pp. 572-584.Applicant
Cacoullos, T., “Estimation of a Multivariate Density”, Annals of The Institute of Statistical Mathematics, The Institute of Statistical Mathematics, vol. 18, No. 2, 1966, pp. 179-189.Applicant
Clark, R.D., “OptiSim: An Extended Dissimilarity Selection Method for Finding Diverse Representative Subsets”, Journal of Chemical Information and Computer Sciences, American Chemical Society, vol. 37, No. 6, 1997, pp. 1181-1188.Applicant
Clark, D. E., and Westhead, D.R., “Evolutionary algorithms in computer-aided molecular design”, Journal of Computer-Aided Molecular Design, ESCOM Science Publishers B.V., vol. 10, No. 4, Aug. 1996, pp. 337-358.Applicant
Cramer, III, R. D. et al., “Comparative Molecular Field Analysis (CoMFA). 1. Effect of Shape on Binding of Steroids to Carrier Proteins”, Journal of The American Chemical Society, American Chemical Society, vol. 110, No. 18, Aug. 31, 1988, pp. 5959-5967.Applicant
Cramer, III, R. D. et al., “Substructural Analysis. A Novel Approach to the Problem of Drug Design”, Journal of Medicinal Chemistry, vo. 17, No. 5, May 1974, pp. 533-535.Applicant
Crippen, G. M., “Voronoi Binding Site Models”, Journal of Computational Chemistry, John Wiley & Sons, Inc., vol. 8, No. 7, Oct./Nov. 1987, pp. 943-955.Applicant
Friedman, J. H. et al., “An Algorithm for Finding Best Matches in Logarithmic Expected Time”, ACM Transactions on Mathematical Software, Association for Computing Machinery, vol. 3, No. 3, Sep. 1977, pp. 209-226.Applicant
Friedman, J.H., “Fitting Functions To Noisy Data In High Dimensions”, Department of Statistics- Stanford University Technical Report No. 101, (Aug. 1988).Applicant
Gallop, M. A. et al., “Applications of Combinatorial Technologies to Drug Discovery. 1. Background and Peptide Combinatorial Libraries”, Journal of Medicinal Chemistry, American Chemical Society, vol. 37, No. 9, Apr. 29, 1994, pp. 1233-1251.Applicant
Ghose, A. K. and Crippen, G.M., “Use of Physicochemical Parameters in Distance Geometry and Related Three-Dimensional Quantitative Structure-Activity Relationships: A Demonstration Using Escherichia coli Dihydrofolate Reductase Inhibitors”, Journal of Medicinal Chemistry, American Chemical Society, vol. 28, No. 3, 1985, pp. 333-346.Applicant
Good, A.C. et al., “Structure-Activity Relationships from Molecular Similarity Matrices”, Journal of Medicinal Chemistry, American Chemical Society, vol. 36, No. 4, Feb. 19, 1993, pp. 433-438.Applicant
Gordon, E. M. et al., “Applications of Combinatorial Technologies to Drug Discovery. 2. Combinatorial Organic Synthesis, Library Screening Strategies, and Future Directions”, Journal of Medicinal Chemistry, American Chemical Society, vol. 37, No. 10, May 13, 1994, pp. 1385-1401.Applicant
Hartigan, J. A., “Representation of Similarity Matrices By Trees”, Journal of the American Statistical Association, vol. 62, No. 320, Dec., 1967, pp. 1140-1158.Applicant
Hopfinger, A. J., “A QSAR Investigation of Dihydrofolate Reductase Inhibition by Baker Triazines Based upon Molecular Shape Analysis”, Journal of the American Chemical Society, American Chemical Society, vol. 102, No. 24, Nov. 19, 1980, pp. 7196-7206.Applicant
Jackson, R. C., “Update on computer-aided drug design”, Current Opinion in BIOTECHNOLOGY, Current Biology Ltd., vol. 6, No. 6, Dec. 1995, pp. 646-651.Applicant
Kim, K. H., “Comparative molecular field analysis (CoMFA)”, Molecular Similarity in Drug Design, ed. P. M. Dean, Blackie Academic & Professional, 1995, Ch. 12, pp. 291-331.Applicant
Kohonen, T., “Self-Organized Formation of Topologically Correct Feature Maps”, Biological Cybernetics, Springer-Verlag, vol. 43, No. 1, 1982, pp. 59-69.Applicant
Koile, K. and Shapiro, R., “Building A Collaborative Drug Design System”, Proceedings of the 25h Hawaii International Conference on System Sciences, IEEE, 1992, pp. 706-716.Applicant
Kowalski, B. R. and Bender, C. F., “Pattern Recognition. II. Linear and Nonlinear Methods for Displaying Chemical Data”, Journal of the American Chemical Society, American Chemical Society, vol. 95, no. 3, Feb. 7, 1973, pp. 686-693.Applicant
Kruskal, J. B., “Nonmetric Multidimensional Scaling: A Numerical Method”, Psychometrika, vol. 29, No. 2, Jun., 1964, pp. 115-129.Applicant
Lengauer, T. and Rarey, M., “Computational methods for biomolecular docking”, Current Opinion in Structural Biology, Current Biology Ltd, vol. 6, No. 3, Jun. 1996, pp. 402-406.Applicant
Luke, B. T., “Evolutionary Programming Applied to the Development of Quantitative Structure-Activity Relationships and Quantitative Structure-Property Relationships”, Journal of Chemical Information and Computer Sciences, American Chemical Society, vol. 34, No. 6, Nov./Dec. 1994, pp. 1279-1287.Applicant
Martin, E. J. et al., “Does Combinatorial Chemistry Obviate Computer-Aided Drug Design?”m Reviews in Computational Chemistry, VCH Publishers, Inc., vol. 10, 1997, pp. 75-99.Applicant
Martin, E. J. et al., “Measuring Diversity: Experimental Design of Combinatorial Libraries for Drug Discovery”, Journal of Medicinal Chemistry, American Chemical Society, vol. 38, No. 9, Apr. 28, 1995, pp. 1431-1436.Applicant
McMartin, C. and Bohacek, R.S., “QXP: Powerful, rapid computer algorithms for structure-based drug design”, Journal of Computer-Aided Molecular Design, Kluwer-Academic Publishers, vol. 11, No. 4, Jul. 1997, pp. 333-344.Applicant
Mezey, P. G. and Walker, P.D., “Fuzzy molecular fragments in drug research”, Drug Discovery today, Elsevier Science Ltd., vol. 2, No. 4, Apr. 1997, pp. 132-137.Applicant
Müller, K., “On the paradigm shift from rational to random design”, Journal of Molecular Structure (Theochem), Elsevier Science B.V., vol. 398-399, Special Issue, pp. 467-471.Applicant
Myers, P., “The Design Of A Universal, Informer™ Library”, COMBICHEM, Inc., 10 pages, Date unknown.Applicant
Oinuma, H. et al., “Neural Networks Applied to Structure-Activity Relationships”, Journal of Medicinal Chemistry, vol. 33, No. 3, pp. 905-908, (1990).Applicant
Omohundro, S. M., “Burnptrees for Efficient Function, Constraint, and Classification Learning”, Advances in Neural Information Processing Systems 3, Morgan Kaufmann, 1991, 7 pages, unknown.Applicant
Parrill, A. L., “Evolutionary and genetic methods in drug design”, Drug Discovery today, Elsevier Science Ltd., vol. 1, No. 12, Dec. 1996, pp. 514-521.Applicant
Polanski, J., “A Neural network for the simulation of biological systems”, Journal of Molecular Structure (Theochem), Elsevier Science Ltd., vol. 398-399, Special Issue, pp. 565-571.Applicant
Ramos-Nino, M. E. et al., “A comparison of quantitative structure-activity relationships for the effect of benzoic and cinnamic acids on Listeria monocytogenes using multiple linear regression, artificial neural network and fuzzy systems”, Journal of Applied Microbiology, Society for Applied Bacteriology, vol. 82, No. 2, Feb. 1997, pp. 168-175.Applicant
Rogers, D. and Hopfinger, A. J., “Application of Genetic Function Approximation to Quantitative Structure-Activity Relationships and Quantitative Structure-Property Relationships”, Journal of Chemical Information and Computer Sciences, American Chemical Society, vol. 34, No. 4, Jul./Aug. 1994, pp. 854-866.Applicant
Sammon, Jr., J. W., “A Nonlinear Mapping for Data Structure Analysis”, IEEE Transactions on Computers, IEEE, vol. C-18, No. 5, May 1969, pp. 401-409.Applicant
Simon, Z. et al., “Mapping of Dihydrofolate-reductase Receptor Site by Correlation with Minimal Topological (Steric) Differences”, Journal of Theoretical Biology, Academic Press, Inc., vol. 66, No. 3, Jun. 7, 1977, pp. 485-495.Applicant
Smellie, A. S. et al., “Fast Drug-Receptor Mapping by Site-Directed Distances: A Novel Method of Predicting New Pharmacological Leads”, Journal of Chemical Information and Computer Sciences, American Chemical Society, vol. 31, No. 3, Aug. 1991, pp. 386-392.Applicant
Specht, D. F., “A General Regression Neural Network”, IEEE Transactions on Neural Networks, IEEE, vol. 2, No. 6, Nov. 1991, pp. 568-576.Applicant
Svizil, D. et al., “Neural Network Prediction of the Solvatochromic Polarity/Polarizability Parameter πH2”, Journal of Chemical Information and Computer Sciences, American Chemical Society, vol. 37, no. 2, 1997, pp. 338-342.Applicant
Todorov, N. P. and Dean, P. M., “Evaluation of a method for controlling molecular scaffold diversity in de novo ligand design”, Journal of Computer-Aided Molecular Design, ESCOM Science Publishers B.V., vol. 11, 1997, pp. 175-192.Applicant
Torgerson, W. S., “Mulridimensional Scaling: I. Theory and Method”, Psychometrika, The Psychometric Society, vol. 17, no. 4, Dec. 1952, pp. 401-419.Applicant
Vapnik, V., “Principles of Risk Minimization for Learning Theory”, Advances in Neural Information Processing Systems 4, Morgan Kaufmann Publishers, Inc., 1992, pp. 831-838.Applicant
Vapnik, V. and Bottou, L., “Local Algorithms for Pattern Recognition and Dependencies Estimation”, Neural Computation, Massachusetts Institute of Technology, vol. 5, No. 6, Nov. 1993, pp. 893-909.Applicant
Viswanadhan, V. N. et al., “Mapping the binding site of the nucleoside transporter protein: a 3D-QSAR study”, Biochimica et Biophysica Acta, Elsevier Science Publishers B.V., vol. 1039, No. 1, 1990, pp. 356-366.Applicant
Warr, W. A., “Exploiting Molecular Diversity: Small Molecule Libraries for Drug Discovery”, Report of Conference held in La Jolla, California, Jan. 23-25, 1995.Applicant
Westhead, D. R. et al., “A comparison of heuristic search algorithms for molecular docking”, Journal of Computer-Aided Molecular Design, Kluwer Academic Publishers, vol. 11, 1997, pp. 209-228.Applicant
Willett, P., “Genetic algorithms in molecular recognition and design”, Trends in Biotechnology, Elsevier Science Publishers B.V., vol. 13, No. 12, Dec. 1995, pp. 516-521.Applicant
Willettm P. and Winterman, V., “A Comparison of Some Measures for the Determination of Inter-Molecular Structural Similarity Measures of Inter-Molecular Structural Similarity”, Quantitative Structure-Activity Relationships, VCH, vol. 5, No. 1, Mar. 1986, pp. 18-25.Applicant
Zadeh, L. A. “Communication Fuzzy Algorithms”, Information and Control, Academic Press, vol. 12, No. 2, Feb. 1968, pp. 94-102.Applicant
Zadeh, L. A., “Fuzzy Sets”, Information and Control, Academic Press, vol. 8, No. 3, Jun. 1965, pp. 338-353.Applicant
Copy of International Search Report issued Apr. 21, 1998 for Appl. No. PCT/US97/20919, 6 pages.Applicant
Copy of International Search Report issued May 13, 1998 for Appl. No. PCT/US97/20918, 7 pages.Applicant
Aiyama, T. et al., “Neural Networks Applied to Structure-Activity Relationships”, Journal of Medicinal Chemistry, American Chemical Society, vol. 33., No. 3, 1990, pp. 905-908.Applicant
Gasteiger, J. et al., “Analysis of the Reactivity of Single Bonds in Aliphatic Molecules by Statistical and Pattern Recognition Methods,” Journal of Chemical Information computer Sciences, American chemical Society, vol. 22, No. 3, 1993, pp. 385-394.Applicant
Gues, A. and Nevo, I., “Neural networks and fuzzy logic in clinical laboratory computing with application to integrated monitoring,” Clinica Chimica Acta, Elsevier Science Publishers B.V., vol. 248, 1996, pp. 73-90.Applicant
Rouvray, D.H., “Similarity in Chemistry: Past, Present and Future,” Topics in Chemistry, Springer-Verlag, vol. 173, 1995, pp. 1-30.Applicant
de Ridder, D. and Duin, R.P.W., “Sammon's mapping using neural networks: A comparison,” Pattern Recognition Letters, Elsevier Science Publishers B.V., vol. 18, No. 11-13, 1997, pp. 1307-1316.Applicant
Kim, H. et al., “Self-Organized Distributed Networks for Learning Highly Nonlinear Mapping,” Intelligent Engineering Systems Through Artificial Neural Networks, American Society of Mechanical Engineers, vol. 4, Nov. 13-16, 1994, pp. 109-114.Applicant
Pal, N.R. and Eluri, V.K., “Two Efficient Connectionist Schemes for Structure Preserving Dimensionality Reduction,” IEEE Transactions on Neural Networks, IEEE, vol. 9, No. 6, Nov. 1998, pp. 1142-1154.Applicant
Domine, D. et al., “Non-Linear Mapping for Structure-Activity and Structure-Property Modelling,” Journal of Chemometrics, John Wiley & Sons, Ltd., vol. 7, No. 4, Jul.-Aug. 1993, pp. 227-242.Applicant
Hosenpud, J. et al., “The Effect of Transplant Center Volume on Cardiac Transplant Outcome: A Report of the United Network for Organ Sharing Scientific Registry,” Journal of the American Medical Association, American Medical Association, vol. 271, No. 23, Jun. 15, 1994, pp. 1844-1849.Applicant
Kim, J. et al., “Multiple Neural Networks Using The Reduced Input Dimension,” Proceedings of the International Conference on Acoustics, Speech, and Signal Processing (ISASSP), IEEE, Apr. 19-22, 1994, pp. II-601-604.Applicant
Copy of International Search Report issued May 28, 2002 for Appln. No. PCT/US01/08974, 7 pages.Applicant