STARFISH

STARFISH identifies rigidly constrained chromatin substructures from chromosome conformation capture (3C) pairwise proximity data to determine regions that can be reliably embedded in three-dimensional models.

Key Features:

• Graph Rigidity Analysis: Applies graph rigidity theory to identify collections of constraints that render genomic regions sufficiently constrained for unique embedding.
• Pebble Game (Pebble 3D) Algorithm: Implements an efficient and accurate pebble game technique (Pebble 3D) for detecting rigid components in three-dimensional space.
• 3C Data Compatibility: Operates on pairwise proximity measurements obtained from chromosome conformation capture (3C) experiments.
• Constraint Filtering and Detection: Detects sufficiently constrained collections and identifies large rigid components even after stringent filtering of constraints.
• Embedding-independent Assessment: Determines which substructures are supported by interaction constraints without performing an embedding or requiring frequency-to-distance mappings.
• Short-range Interaction Emphasis: Reveals the importance of short-range interactions in establishing chromatin organization and high-confidence regions.

Scientific Applications:

• High-confidence 3D modeling regions: Identifies chromatin substructures that can be reliably embedded into three-dimensional models for downstream structural analysis.
• Interpretation of chromatin organization: Supports studies of long-range gene regulation and chromosome rearrangements by delineating constrained regions in 3C data.
• Pre-processing for hypothesis testing: Provides constraint-based filtering to ensure that correlations between chromatin structure and biological phenomena are not driven by arbitrary unconstrained embeddings.

Methodology:

Applies graph rigidity theory and the Pebble 3D pebble game algorithm to pairwise proximity measurements from 3C experiments to detect rigid components, with optional stringent constraint filtering, and without performing embedding or frequency-to-distance mapping.