GREAC: An Open-source software for Genome Region Extraction and Classification

Technical Summary: GREAC - An Open-source software for Genome Region Extraction and Classification

Problem Statement
The analysis of genomic sequences faces a dual challenge: the exponential growth of high-throughput sequencing data and the computational limitations of traditional alignment-based methods. While alignment-based techniques identify homologous regions, they rely on computationally intensive dynamic programming, creating bottlenecks for large-scale datasets. Conversely, alignment-free methods, particularly those utilizing k-mer frequencies, offer scalability but often exacerbate the "curse of dimensionality" by converting sequences into high-dimensional feature vectors. This high dimensionality increases computational complexity, storage demands, and the risk of overfitting, often obscuring the biological interpretability of results. There is a critical need for methods that reduce dimensionality without losing crucial biological information, while maintaining transparency and explainability in pattern discovery without relying on reference genomes.

Methodology
The authors present GREAC (Genomic Region Extraction and Classifier), a novel, data-driven, alignment-free computational methodology implemented in the Julia language. The approach is designed to identify discriminative genomic regions and classify biological sequences through a three-phase workflow:

1. Variant-Exclusive K-mer Extraction:
   The method begins by identifying k-mers that are unique to specific variants within the input dataset. Unlike approaches that compare against a reference genome, GREAC derives these k-mers solely from the inherent information of the input sequences. It employs a maximum entropy function (similar to GRAMEP) to select the most informative k-mers, ensuring that only k-mers uniquely exclusive to a single variant are retained, thereby eliminating shared or non-discriminative sequences.

2. Discriminative Region Identification:
   Using a sliding-window approach, the algorithm scans the genome to locate regions containing the identified exclusive k-mers. The window size is calculated as a percentage of the shortest sequence length in the dataset to accommodate length variations. A positional counter generates a frequency histogram for each variant; regions exceeding a specific appearance threshold across training samples are selected as discriminative. To handle sequence length deviations, a safety margin is applied during extraction. These selected regions are then unified into a positional conjunction to ensure consistent representation across variants.

3. Signal Construction and Classification:
   The method constructs a reference signal profile for each variant based on the relative frequency of k-mers within the extracted regions. For classification, GREAC calculates the distance between a new sequence's signal and the reference distributions using the Manhattan distance.

   • Classification Strategies: The paper evaluates two classification approaches. The first utilizes a Gaussian membership function to assign probabilistic belonging scores based on distance. The second, which was selected for the final implementation due to performance and deployment constraints, employs a Random Forest classifier. This tree-based approach utilizes features derived from the reference signals, including membership values and signal divergence (variations between consecutive windows), to achieve high accuracy.

Key Contributions

• Dimensionality Reduction: GREAC significantly reduces the data volume required for analysis by focusing only on informative genomic regions rather than entire sequences.
• Reference-Free Operation: The method operates without the need for a reference genome, eliminating bias introduced by reference selection and enabling the analysis of novel or highly divergent sequences.
• Explainability: By directly extracting discriminative k-mers and mapping them to specific genomic coordinates, GREAC provides transparent results. The identified regions can be directly correlated with biological features (e.g., coding sequences, regulatory elements).
• Open-Source Implementation: The software is freely available, modular, and designed for community adaptation, with built-in functions for feature extraction, parameter fitting, benchmarking, and classification.

Results
The methodology was validated on five diverse viral datasets: SARS-CoV-2, HIV-1, Dengue (DENV), Hepatitis B (HBV), and Monkeypox. Key findings include:

• Classification Performance: GREAC demonstrated robust performance across all datasets. In comparative tests against KEVOLVE and CASTOR-KRFE, GREAC achieved mean F1-scores ranging from 95.95% (SARS-CoV-2) to 98.90% (HBV and HIV). Notably, GREAC outperformed KEVOLVE significantly across all datasets (e.g., 95.95% vs. 4.82% for SARS-CoV-2) and generally matched or exceeded CASTOR-KRFE, particularly in scenarios with limited training data where KEVOLVE struggled.
• Dimensionality Reduction: The method achieved substantial data compression for larger genomes. It reduced the SARS-CoV-2 dataset by approximately 67.8% and the Monkeypox dataset by 72.2%. For smaller genomes (HBV, HIV, DENV), the reduction was marginal (approx. 100 nucleotides), reflecting the method's ability to preserve dense information in compact genomes while compressing redundant data in larger ones.
• Biological Relevance: The extracted regions showed significant overlap with known functional elements. For SARS-CoV-2, regions were predominantly located in coding sequences of structural proteins. For HBV and DENV, regions were distributed throughout the genome, aligning with known genic regions and RNA secondary structures. The identified regions also overlapped with high-frequency mutational events reported by Nextstrain.

Significance
The paper positions GREAC as a tool that addresses the critical need for explainability and transparency in genomic analysis. By focusing on informative regions rather than whole sequences, the method bridges the gap between high-performance machine learning and biological interpretability. The authors claim that GREAC offers a scalable, data-driven solution that eliminates dependence on reference genomes, making it suitable for detecting viral variants, characterizing mutation behaviors, and understanding evolutionary mechanisms such as speciation and population differentiation. The open-source nature of the software ensures replicability and facilitates the development of tailored biotechnology applications.