Introduction
In scientific domains such as bioinformatics and fluid dynamics, spatial data mining is essential for discovering relationships between complex features like protein substructures or fluid vortices. Traditionally, these features have been simplified into single points, a representation that discards critical information regarding shape, size, and orientation. This paper introduces a framework for mining Spatial Object Association Patterns (SOAPs) by treating features as geometric objects with extent rather than simple coordinates.
Modeling Geometric Extents
To capture the nuances of scientific features, the authors move beyond point-representations. Features are modeled as geometric primitives: parallelograms are used for protein structures, while ellipses are ideal for fluid vortices. This approach allows the system to account for the "spine" or orientation of a feature, which is often as important as its location in determining its function or behavior.
Spatial Object Association Patterns (SOAPs)
The framework defines two primary pattern types to describe the structural signatures of these objects:
- Star SOAPs: These consist of a central object-type surrounded by several neighboring object-types.
- Sequence SOAPs: These represent a chain of objects that follow a specific spatial order, often defined by directional constraints like
isAboveorisLeftOf.
To measure relationships between these shapes, the authors introduce object-oriented distance metrics. The Line-Line (L-L) distance, which measures the shortest distance between the major axes (mid-lines) of two objects, proved particularly effective. It consistently discovered more meaningful patterns than standard point-to-point or boundary-to-boundary metrics because it accounts for the orientation of the underlying structures.
Mining and Validation
The mining process utilizes an equivalence-class based approach to efficiently identify frequent patterns across large datasets. To ensure the discovered patterns are biologically or physically significant, the authors employ entropy-based pruning, which filters out patterns that are randomly distributed in favor of those specific to certain classes.
The framework was evaluated on 8,732 protein contact maps from the Protein Data Bank (PDB), involving over 1 million extracted features. By validating against the SCOP (Structural Classification of Proteins) database, the authors demonstrated that specific SOAPs act as unique "fingerprints" for protein folds. For example, the algorithm identified 170 unique SOAPs in $\beta$-proteins, providing a much richer set of features for classification than point-based methods.
Conclusion and Future Directions
The shift from point-based to object-oriented spatial mining provides a significantly more descriptive set of features for scientific classification. While the current model uses parallelograms and ellipses, future work may incorporate more complex "landmark" based representations for highly irregular shapes. Additionally, extending this framework to spatio-temporal data would allow for reasoning about how these object associations evolve over time in dynamic systems like fluid flows.
Summary updated