SSKDSP

SSKDSP implements a scalable similarity-search approach that combines a modified Single Source K Diverse Shortest Paths (SSKDSP) algorithm with the Enrichment of Network Topological Similarity (ENTS) algorithm to improve protein-fold recognition and protein structure prediction using sequence and structural similarity metrics.

Key Features:

• Enhanced Efficiency: The modified SSKDSP algorithm reduces memory usage by 82% and execution time by 61%, enabling analysis of larger and denser graphs.
• Integration with ENTS: Combines SSKDSP with the Enrichment of Network Topological Similarity (ENTS) algorithm to produce statistically ranked fold predictions from a graph-based feature space built from sequence and structural similarity metrics.
• Superior Performance: Benchmarking on 600 query proteins shows the ENTS-SSKDSP method outperforms HHSearch and Sparks-X in protein structure prediction tasks.
• Scalability and Versatility: Scalable implementation supports adaptation to other similarity-search problems, including applications in chemoinformatics.

Scientific Applications:

• Protein Structure Prediction: Addresses the fold recognition problem to support prediction of protein structures using combined sequence and structural similarity within a graph framework.
• Graph-Based Search Optimization: Identifies diverse shortest paths and ranks similarity within large, complex graphs for comparative analyses.
• Chemoinformatics Similarity Search: Applies graph-based similarity and statistical ranking approaches to chemical similarity-search problems.

Methodology:

Construct a graph feature space from sequence and structural similarity metrics; use the Single Source K Diverse Shortest Paths (SSKDSP) algorithm to identify diverse shortest paths from a single source; apply the Enrichment of Network Topological Similarity (ENTS) algorithm to assess statistical significance of fold rankings.