MotifCut 0.1 beta

MotifCut 0.1 beta formulates DNA motif discovery as a graph-theoretic maximum density subgraph problem on k-mers to identify regulatory sequence motifs via convex optimization.

Key Features:

• Graph-Theoretic Framework: Constructs a graph with vertices representing k-mers from input DNA sequences and edges defined by pairwise k-mer similarity.
• Maximum Density Subgraph Formulation: Casts motif finding as a maximum density subgraph problem and solves it as a convex optimization with a polynomial-time solution.
• Flexible Motif Modeling: Makes no stringent structural assumptions, enabling detection of motifs compatible with position-specific scoring matrices (PSSMs) and motifs with dependencies between positions.
• Scalability and Comparative Performance: Demonstrated scalability with increasing input sizes and the ability to discover motifs not identified by other methods through benchmarking on synthetic and real datasets.

Scientific Applications:

• Regulatory Element Discovery: Identification of DNA regulatory motifs to provide insights into gene regulation mechanisms.
• Dataset Analysis and Benchmarking: Analysis and comparison on synthetic datasets and real biological data, including yeast motifs, for motif discovery and method evaluation.

Methodology:

Build a graph by representing each k-mer as a vertex and adding edges based on similarity metrics between k-mers; search for the maximum density subgraph via convex optimization to identify clusters of similar k-mers; benchmark performance on synthetic and real datasets to assess scalability and motif recovery.