GFA Graph Processing & K-mer Pattern Matching (C++)

This repository contains the C++ source code developed for the final assignment of the Algorithms and Data Structures course.

The project implements a complete pipeline for processing genomic graphs in GFA format, converting cyclic directed graphs into Directed Acyclic Graphs (DAGs), exploring paths, and performing string matching algorithms.

🧮 Implementation & Technical Highlights

Based on the source code (main.cpp), the project implements the following custom logic:

1. GFA File Parsing & Reverse Complement Support:

   • Double-pass file parsing using std::ifstream and string streams to dynamically size arrays based on segment indices.
   • Direct handling of oriented links (+ / -). Links with reverse orientation (-) are mapped to additional nodes representing the Reverse Complement sequence via a custom transformation algorithm.

2. Cycle Detection & Topological DAG Reduction:

   • Implementation of DFS_Cycle using recursion and back-tracking flags (ricorsivo) to detect cycles.
   • Automatic back-edge identification and removal (edgeToRemove) via std::remove on adjacency lists to guarantee a Directed Acyclic Graph structure.

3. Graph Normalization (Node Splitting):

   • Includes a graph transformation step (trasformazioneGrafo) that breaks multi-character label nodes into linear chains of single-character nodes, enabling uniform path length traversals.

4. Source-to-Sink Path Exploration & Rolling Hash Search:

   • Dynamic identification of source nodes ($\text{inDegree} = 0$).
   • Recursive DFS path discovery with backtrack string popping (currentPath.erase).
   • Pattern matching via Rolling Hash (using base $257$ and modulo $10^9 + 7$) to search for arbitrary $K$-mer strings across all path combinations.

5. Top-N $K$-mer Frequency Analysis (Bonus Requirement):

   • Includes findTopNStrings to extract and rank the top 10 most frequent sub-sequences of specified length $N$ across the graph topology using hash maps and sorting routines.

📂 Repository Structure

├── src/
│   └── ASD-project.cpp         # Complete C++ source code containing all pipeline steps
│   └── project.exe         # Compiled source
├── docs/
│   └── project-instructions.url   # Link/Reference to the full assignment specifications
└── graphs/
    └── DRB1.gfa   # Sample GFA graph file for testing and validation