Stepgram

Stepgram detects DNA copy-number aberrations from array-based comparative genomic hybridization (aCGH) data to identify genomic amplifications and deletions relevant to cancer genomics.

Key Features:

• High-Resolution Analysis: Processes microarray fluorescence ratios from BACs, cDNA, or oligonucleotide probes to map DNA copy-number changes at high resolution.
• Statistical Framework: Formulates DNA copy-number analysis as optimization problems over real-valued signal vectors to identify significant biological structures by maximizing mathematical functions of signal intensity and interval size.
• Optimization Algorithm: Implements a linear-time approximation scheme with time complexity O(n epsilon^{-2}) that identifies intervals maximizing phi(I) = Sigmanu(i)/sqrt(|I|) within a multiplicative factor alpha(epsilon) of the optimum as epsilon approaches zero.
• Performance Enhancement: Reduces computational cost by orders of magnitude compared to naive quadratic approaches through algorithmic optimizations.
• Benchmarking and Validation: Algorithms have been benchmarked using synthetic data and publicly available DNA copy-number datasets.

Scientific Applications:

• Aberration Detection: Detects copy-number aberrations within single aCGH samples to pinpoint amplifications and deletions.
• Common Alteration Identification: Identifies common alterations across fixed sets or subsets of samples, enabling detection of shared genomic changes such as those observed in breast cancer.

Methodology:

Transforms aCGH-derived copy-number signals into optimization problems over real-valued vectors and applies a linear-time approximation scheme to maximize the interval scoring function phi(I) = Sigmanu(i)/sqrt(|I|) with time complexity O(n epsilon^{-2}).