CAMELLIA: an alignment-free pipeline integrating k-mer feature selection and supervised classification for genomic sequence subtyping Authors: Tatiana Mari Saita, Matheus Henrique Pimenta-Zanon, Artur Trancoso Lopo de Queiroz, Glaucia Maria Bressan, Fabricio Martins Lopes Published: 2026 ABSTRACT AbstractScalable analysis of biological sequences is essential for functional characterization, biomarker discovery, and therapeutic and vaccine development. Alignment-based pipelines often fail to capture intraspecific variation and become computationally limited on large datasets, while alignment-free methods treat each class as homogeneous, ignoring sample heterogeneity. We present CAMELLIA (Combining AlignMent-free fEature seLection cLassIficAtion), an alignment-free framework that combines feature selection with explainable machine learning for genomic sequence analysis and classification. CAMELLIA identifies subgroups within classes and ensures underrepresented subgroups are captured by the selected features, yielding a more accurate and scalable data-driven representation. Sequences are represented as graphs, from which structural patterns are extracted as features for supervised classifiers, enabling accurate class discrimination. In an HIV-1 case study, CAMELLIA accurately classified sequences into eight subtypes, reduced processing time versus MEGA (MUSCLE) and FAMSA, matched CASTOR-KRFE under identical splits, and outperformed COMET and REGA in accuracy. Beyond predictive performance, CAMELLIA recovered structural patterns beyond class labels, improving feature selection and interpretability. We further examined feature-count sensitivity, showing how selected feature numbers relate to underfitting or noise-driven overfitting. By balancing scalability, accuracy, and interpretability, CAMELLIA offers a new lens for genomic sequence classification and sets a new standard for data-driven, heterogeneity-aware analysis. Introduction Bioinformatics integrates concepts from biology, computer science, and mathematics to analyse biological data at an ever-increasing scale. A primary challenge is managing the rapid generation of heterogeneous data, particularly biological sequences, which demands computational methods that are robust, scalable, and aligned with FAIR principles (Findability, Accessibility, Interoperability, and Reusability) [1]. Sequence analysis remains a cornerstone of bioinformatics, as genetic information is encoded in the order of nucleotides and amino acids. Comparing sequences allows for the identification of similarity patterns that inform evolutionary relationships and reveal variations associated with specific phenotypes [2]. Mutational processes are the primary driver of evolution, and changes in genetic variation can modify pathogen traits such as virulence and transmissibility, with direct consequences for public health [3]. Two broad strategies have been employed for sequence comparison: alignment-based and alignment-free methods (AF) [4]. Alignment-based approaches compare sequences position-by-position to identify homology [5], but their computational cost scales quadratically with dataset size and their accuracy degrades for highly divergent or recombinant sequences. AF approaches represent sequences using numerical or structural descriptors, such as k-mer frequencies to estimate similarity without requiring explicit positional correspondence, and are therefore intrinsically scalable [6–8]. Sequence comparison can be applied to problems involving intraspecific variability: sequences within the same biological category may exhibit heterogeneous patterns arising from mutation, recombination, or horizontal gene transfer. In this context, supervised machine learning (ML) provides a principled way to handle this complexity by learning non-linear classification boundaries from features derived from sequences [9]. To address these challenges, we propose CAMELLIA (Combining AlignMent-free fEature seLection cLassIficAtion), an integrated pipeline that explicitly incorporates intraclass k-mer diversity. CAMELLIA represents sequences as weighted adjacency matrices encoding neighbourhood relationships among k-mers, thereby enabling scalable comparisons without positional alignment. Unlike generic dimensionality reduction techniques such as principal component analysis (PCA), which treat samples within classes as a whole and maximize global variance, or univariate filters that ignore feature interactions, CAMELLIA employs a cluster-aware feature selection strategy. By first performing clustering analysis on adjacency matrix representations, the method identifies informative k-mers within specific clusters, ensuring that the classifier captures relevant, fine-grained features of each cluster inside the classes [10]. This conceptual advance ensures that no subclass is lost during aggregation, enabling a more faithful and nuanced representation of the underlying biological variation, thereby capturing the complexity of genomic samples and providing a more comprehensive basis for downstream classification and interpretation. Classification is performed using two ensemble methods: Random Forest (RF) [11] and Extreme Gradient Boosting (XGBoost) [12]. Beyond predictive performance, the selected k-mers provide an interpretable layer that identifies which sequence patterns are most informative for each class and cluster, supporting biologically transparent model behaviour. As a case study, CAMELLIA was assessed by considering genomic sequences of Human Immunodeficiency Virus type 1 (HIV-1), the causative agent of Acquired Immunodeficiency Syndrome (AIDS). HIV-1 represents a paradigmatic challenge for sequence classification: its error-prone reverse transcriptase (RT) generates an exceptionally high mutation rate, producing extensive intrasubtype sequence diversity and a complex landscape of recombinant forms that fundamentally challenge alignment-dependent classification systems [13]. Subtype-specific sequence characteristics can influence transmissibility, disease progression, and response to antiretroviral therapy, making reliable automated subtyping a prerequisite for targeted therapeutic and vaccine design. By focusing on cluster and class-associated k-mer patterns, CAMELLIA offers a practical framework for improving subtype classification and highlighting sequence signatures that can guide downstream biological analyses. The assessment also considered other methods from the literature regarding feature-count sensitivity; comparative benchmarks against AF feature extraction methods: Frequency Chaos Game Representation (FGCR) [14], Return Time Distribution (RTD) [15], KMER, and Spaced Word Frequencies (SWF) [16]; AF viral classification approaches: CASTOR-KRFE [17] and COMET [18], a phylogenetics-based tool: REGA [19], and two alignment-based methods: FAMSA [20] and MEGA [21]. CAMELLIA presents three principal methodological contributions. The quota-based feature selection (Algorithm 2) reduces computational cost during training while improving discriminative power by dividing the feature selection problem according to clusters defined for each class (genome type), rather than using class labels alone. This distinction is important for organisms with high mutation rates, such as HIV-1, in which sequences from the same subtype may exhibit sufficient internal divergence to form distinct structural sub-groups. By selecting k-mers that represent patterns within each cluster, CAMELLIA captures intraspecific variation that would be systematically missed if feature selection were guided exclusively by class membership, precisely because those fine-grained patterns do not dominate the class-level signal but are nonetheless essential for distinguishing divergent sequence variants. This cluster-stratified strategy differs fundamentally from approaches such as CASTOR-KRFE [17], which select features globally from a fixed reference set and therefore cannot represent intraclass structural heterogeneity. Beyond feature selection, CAMELLIA provides genomic positional mapping of the selected k-mers back to reference coordinates, enabling direct annotation against known functional regions, a capability absent from most existing AF classifiers. The pipeline further integrates graph-based sequence representation, cluster-aware feature selection, and ensemble supervised learning into a single, user-trainable pipeline that accepts standard FASTA input and is distributed as an open-source R package. Together, these contributions address three principal bottlenecks in scalable sequence classification: computational efficiency in training (reduced by cluster-stratified feature selection, which constrains the search space to structurally coherent subsets), biological interpretability (provided by positional k-mer mapping), and robustness to within-class heterogeneity (managed by ensuring that divergent intraspecific clusters are represented in the feature set). Related work Genomic sequence classification methods are broadly categorized into alignment-based, phylogenetic, and AF methods, each presenting distinct trade-offs in computational efficiency, interpretability, and scalability. Alignment-based methods rely on direct positional comparison to identify homology. General-purpose tools such as BLAST [22] and USEARCH [23], as well as distance-driven methods such as PASC [24], remain widely used. However, their computational requirements are often prohibitive for large-scale analyses [4], and their reliance on linear alignment assumptions renders them sensitive to recombination, genome shuffling, and horizontal gene transfer, all of which are common in viral evolution [25]. Phylogenetic methods classify sequences by placing them in an evolutionary context, typically by inserting query sequences into a fixed reference topology. Tools such as Pplacer [26] use maximum likelihood for this placement, offering rich evolutionary interpretability but at high computational cost. AF methods have emerged as scalable alternatives to alignment-based approaches, representing sequences as numerical vectors, most commonly k-mer frequency distributions, and enabling comparisons without explicit positional matching [27]. In viral classification, combining AF representations with clustering and supervised learning has gained traction [28]. CASTOR-KRFE [17] demonstrated that selecting discriminative subsequences from reference pathogen sequences can enhance both accuracy and interpretability. More recently, the field has been profoundly influenced by deep learning approaches that treat nucleotide sequences as natural language. ML has expanded sequence analysis by learning non-linear decision boundaries from feature representations. Once sequences are encoded as numerical vectors, ML models can capture complex dependencies beyond simple distance metrics. Recent surveys have underscored this trend in virology, notably in Severe Acute Respiratory Syndrome Coronavirus 2 (SARS-CoV-2) variant classification [29]. A persistent challenge, however, is selecting features that remain informative across heterogeneous classes where discriminative signals may be sparse or distributed across multiple genomic scales. Several AF approaches, including Frequency Chaos Game Representation (FCGR), k-mer composition, Return Time Distribution (RTD), and Spaced Word Frequencies (STW), have been used in combination with ML methods for the classification of viral genomic sequences, achieving high-accuracy classification of viruses such as SARS-CoV-2, Dengue virus (Denv), and HIV-1 [30]. More recently, deep learning approaches have been applied to sequence classification, offering substantially increased model capacity at the cost of interpretability and computational requirements. DNABERT-2 [31] adapts transformer architectures with multi-species tokenization for genomic sequences, achieving strong performance on classification tasks but requiring GPU infrastructure, large pre-training corpora, and fine-tuning procedures that are impractical for users without machine learning expertise. Similarly, the Nucleotide Transformer [32] and HyenaDNA [33] follow a similar pre-training paradigm, with the added constraint that applying them to specialized subtyping tasks with user-defined training sets requires substantial fine-tuning effort, and the learned representations offer limited traceability to identifiable sequence patterns. In the context of HIV-1, automated subtyping tools are essential because manual classification is infeasible for modern sequencing datasets. Available systems span similarity-based methods (e.g. the National Center for Biotechnology Information (NCBI) genotyping tool [34], Stanford HIV Drug Resistance Database, Geno2pheno), statistical modelling approaches (e.g. COMET [18]), and phylogenetic methods (e.g. REGA [35] and SCUEAL). Despite this diversity, HIV classification remains challenging owing to extensive intra-subtype diversity driven by mutation and recombination, which increases the risk of ambiguous or incorrect assignments, motivating the development of scalable approaches capable of reliably identifying sequence patterns that differentiate subtypes. More recently, deep learning has also been explored specifically for HIV-1 subtyping: using Word2Vec-based embeddings across multiple classifiers [36], achieving an accuracy of 0.84 across both common and underrepresented subtypes; however, features were selected globally from flat frequency vectors without accounting for intraspecific structural heterogeneity, and no mapping of discriminative features to genomic coordinates was provided. HIV-1-M-SPBEnv [37] addressed the small-sample challenge inherent to deep learning, achieving perfect precision, recall, and F1-score across 12 Group M subtypes on an independent test set; despite this accuracy, the method is restricted to the env gene region and relies on synthetic data augmentation to overcome the scarcity of real, labelled sequences. This study introduces CAMELLIA, a novel method that integrates AF sequence representation with cluster-aware feature selection to support robust, interpretable, and computationally efficient supervised classification. This method operates on whole-genome sequences of different lengths without restricting analysis to a specific genomic region, requires no synthetic data augmentation, performs on standard CPU hardware, and yields explicitly interpretable k-mer features that can be mapped to specific genomic coordinates, properties that are collectively absent from the approaches described above. Framework A genetic mutation is any heritable modification in an organism’s genome that is not attributable to recombination. Although all organisms accumulate mutations through normal cellular processes or environmental interactions, RNA viruses exhibit exceptionally high substitution rates of approximately to per base pair per generation [38], several orders of magnitude higher than bacteria () or human somatic cells (). This genomic plasticity enables rapid adaptation to selective pressures, generating extensive sequence heterogeneity that complicates automated classification. The focal organism is HIV-1, responsible for the global AIDS pandemic [39]. The HIV-1 genome comprises approximately 10 000 base pairs encoding three major polyproteins (Gag, Pol, Env) and several regulatory proteins [40]. The absence of proofreading in RT results in a diverse intrahost population (a quasispecies). HIV-1 Group M, the driver of the global epidemic, comprises multiple pure subtypes (A1, A2, A3, A4, A6, A7, A8, B, C, D, F1, F2, G, H, J, K, and L, the last described in 2019 [41]); historical subtypes E and I have been reclassified as circulating recombinant forms [42]. Beyond pure subtypes, recombination yields Circulating Recombinant Forms (CRFs), stable lineages identified in three or more epidemiologically unlinked individuals (e.g. CRF01_AE), and Unique Recombinant Forms (URFs), which lack established circulation patterns. The Los Alamos HIV Database currently catalogues over 170 CRFs. Recent epidemiological surveys indicate that recombinants account for approximately 29% of global infections, potentially surpassing major pure subtypes in some regions [43, 44], a diversity that profoundly challenges static, alignment-based classification systems. In 2025, an estimated 41 million people were living with HIV, with the highest burden in Southern Africa [45]. Yet high-quality genomic data remain unevenly distributed, historically biased towards Western populations in which subtype B is more prevalent. This ‘subtype B bias’ limits the effectiveness of therapeutic and vaccine design for non-B subtypes (e.g. subtype C in Africa and India), as genetic differences among subtypes can influence antiretroviral therapy (ART) susceptibility and disease progression. Geographically, subtype C predominates in Southern Africa and India, subtype A in Eastern Europe, subtype B in the Americas and Western Europe, while newer subtypes (J, K, L) appear mainly in Central Africa [44]. A critical computational challenge is that many classification tools rely on complete metadata for accurate subtyping. In many settings, contextual variables (geographic origin, risk group, and transmission route) are either missing or unavailable at the time of sequencing. This sparsity limits the applicability of Bayesian or phylogenetic methods that depend on strong prior information. An AF framework that identifies intrinsic k-mer patterns enables fully data-driven classification that is robust to missing metadata, while still permitting the incorporation of epidemiological variables post-classification to enhance biological interpretation. Sequence comparison AF techniques fall into two broad categories: subsequence statistics (e.g. word counting) and descriptors derived from sequence transformations [4]. The appropriate choice depends on the biological question and the distance metric employed. To improve this scenario, this study is based on a well-established complex network theory [46]. Inspired by BASiNET [47], in this study, the genomic sequences are modelled as directed graphs in which vertices represent k-mers, and edges encode transitions between consecutive k-mers, preserving order information. This representation captures local sequence patterns, including repeated transitions (self-loops) and connectivity patterns among viral subtypes. Formally, a sequence graph G=(V, E) consists of a vertex set V and a set of directed edges E, where an edge from vertex i to vertex j exists if subsequence j immediately follows i in the biological sequence. This structure is quantified using a weighted adjacency matrix A, where each entry corresponds to the frequency of the transition i → j. The graph adjacency matrix provides a compact numerical encoding of topological properties [48, 49]. The dissimilarity between two sequences can be obtained using the following distance measures: Bray-Curtis, Euclidean, Frobenius, Hamming, and Jaccard, as described in the Supplementary File S1, computed using the distance functions implemented in the R packages vegan and NetworkDistance. Smaller values indicate similar underlying connectivity patterns, reflecting biological relatedness. Sequence classification Sequence classification involves unsupervised and supervised learning. Unsupervised clustering groups sequences based on intrinsic similarity, independent of class labels, revealing latent structure in the input data. Supervised learning then exploits this structure through feature selection and model training. Feature selection is a dimensionality-reduction step that removes redundant or noisy variables, improving generalization and computational efficiency [50], which is successfully applied in bioinformatics applications [51, 52]. In the CAMELLIA method, feature selection is based on clustering the adjacency matrix representations of sequences, capturing sequence-specific features within each group and its corresponding class. Although PCA reduces dimensionality by constructing orthogonal components that maximize global variance [53], the resulting components are linear combinations of all original features, obscuring the biological identity of informative k-mers, which retain interpretable k-mer identities associated with specific subtypes and clusters. Supervised ML refers to a class of algorithms that learn a mapping from input features to predefined class labels by optimizing a classification objective on a set of labelled training examples. Once trained, the model generalizes this mapping to previously unseen samples, assigning class predictions based on the patterns captured during training. In the context of genomic sequence classification, supervised learning operates on numerical feature vectors derived from the raw sequence, such as k-mer frequency distributions. Many classification algorithms are available in the literature. However, this study focuses on explainability and adopts Ensemble classifiers, namely Random Forest (RF) [11] and XGBoost (XGB) [54], which are examples of explainable supervised classification. These two algorithms are selected over alternatives such as Support Vector Machines (SVM) or LightGBM based on their demonstrated suitability for the high-dimensional, sparse feature spaces property of k-mer-based genomic representations [55]. RF aggregates predictions from multiple independent decision trees, mitigating overfitting and providing robust embedded feature importance estimates [56]. XGB builds trees sequentially to minimize a regularized loss function, handles sparse input features natively, and offers superior performance on structured tabular data, properties that translate into advantages in viral genomic classification tasks [57]. Furthermore, a systematic benchmark of AF methods for HIV-1 subtype classification demonstrated that a k-mer XGBoost model achieved the highest balanced accuracy across common and underrepresented subtypes, outperforming SVM and natural vector-based approaches on the same task [36]. LightGBM, although faster on very large datasets, has been shown to underperform relative to XGBoost on moderate-sized structured problems with class imbalance [57]. Model performance can be evaluated using accuracy, precision, recall, and F1-score [58]. Beyond accuracy, a key advantage of CAMELLIA is explainability: using k-mers and their transitions as features enables the identification of specific sequence patterns driving classification decisions. Discriminative k-mers can be mapped back to reference genomes to assess correspondence with known functional regions or mutations, a capability essential for clinical and epidemiological translation, where ‘black-box’ predictions are insufficient without biological justification. Materials and methods CAMELLIA brings together an AF sequence representation, unsupervised clustering, and supervised learning into a cohesive method for viral subtyping analyses and classification. The overview is illustrated in Fig. 1. Schematic workflow of the CAMELLIA pipeline. Step 1 (Representation): Sequences in fasta files are transformed as graphs. Step 2 (Edge frequencies): The frequencies of edges generate adjacency matrices. Step 3 (Clustering): Pairwise distances between adjacency matrices drive hierarchical clustering, producing a dendrogram that reveals latent class structure. Step 4 (Feature Selection): Discriminative k-mers are selected based on their normalized occurrence within clusters and subtypes using a quota-based algorithm. Step 5 (Classification): Selected features train RF and XGB models to predict viral subtypes, evaluated by accuracy, precision, recall, and F1-score. Step 6 (Interpretation): Positional analysis maps discriminative k-mers back to reference genome coordinates to identify functional relevance. Graph-based sequence representation The sequence representation step is based on the BASiNET method [47], which transforms each genomic sequence into a directed graph encoding the nucleotide’s structural organization. Vertices represent nucleotide subsequences of length W extracted by a sliding window with step size S=1. In this study, W=3 (trinucleotides), yielding possible vertices. The choice of W=3 is motivated by trinucleotides corresponding directly to codons, the fundamental unit of the genetic code, in which each group of three consecutive nucleotides encodes a specific amino acid or a stop signal. The selected features retain a direct biological interpretation: recurrent transitions between specific codons can be linked to amino acid usage patterns, codon bias, and protein-level functional constraints that are characteristic of each viral subtype. Furthermore, W=3 yields a tractable feature space of possible transitions, balancing representational richness against computational cost. Larger values of W increase this space exponentially, leading to progressively sparser adjacency matrices and substantially higher memory and runtime requirements during pairwise distance computation and clustering, without producing commensurate gains in classification accuracy. Smaller values (W=2) reduce the feature space to 256 transitions, which proved insufficient to capture the subtype-discriminative structural patterns present in the HIV-1 dataset. For every pair of consecutive k-mers in the sequence, a directed edge connects the antecedent to the subsequent k-mer. The resulting graph is encoded in an adjacency matrix whose entries record transition frequencies between specific k-mers. The high-frequency transitions indicate recurrent structural patterns characteristic of the genome. The matrix dimensions are fixed at regardless of input sequence length, enabling direct comparisons across sequences of varying sizes. Adjacency matrices are vectorized (flattened row-wise) to optimize the calculation, producing -dimensional feature vectors. A symmetric pairwise distance matrix is then computed using the adopted metrics (see Supplementary File S1) for all pairs. Clustering and structural analysis Unsupervised clustering is applied to the distance matrix to reveal intrinsic groupings. The classical Ward’s method [59], a hierarchical agglomerative algorithm that minimizes within-cluster sum of squared deviations, produces a dendrogram whose leaves correspond to labelled sequences. Clusters are defined as biologically meaningful under a homogeneity criterion: each cluster must exhibit a dominant subtype frequency exceeding a threshold θ (default θ = 0.7, values closer to 1.0 indicate that the cluster contains more elements from a single subtype), which aims to capture more specific characteristics of the sequences composing the cluster with respect to their class distribution. Algorithm 1 traverses the dendrogram to identify such groups while preserving their hierarchical structure. Within each cluster, a consensus adjacency matrix is obtained by summing the constituent sequences’ adjacency matrices. This aggregate highlights persistent k-mer transitions characteristic of the subtype group and serves as the basis for feature selection. Feature selection and supervised classification Using the full feature space, possible transitions for W=3 may introduce noise and unnecessary computational overhead. CAMELLIA, therefore, applies the quota-based feature selection strategy described in Algorithm 2, which derives a compact set of highly discriminative k-mers by ranking candidates according to their normalized occurrence in cluster consensus matrices. The selected features are used as input for supervised classification with RF and XGB. Model performance was assessed via 10-fold cross-validation on the training set, and final generalization was evaluated on a hold-out test set. The training dataset employed in this study is identical to that utilized during the clustering and feature selection phase, thereby preventing data leakage in feature engineering and simultaneously reducing computational processing time when training on large sequence datasets. The discriminative k-mers produced by the feature selection step can be mapped back to genomic coordinates to support biological interpretation. For a given reference sequence, the method records the chromosomal start and end positions of each selected k-mer, enabling downstream annotation against known functional regions (e.g. LTR, gag, pol, env in HIV-1). Application To make the computational requirements for CAMELLIA clear, all computational experiments were performed on a workstation equipped with an Intel Core i7-7700K processor (four cores, 4.2 GHz) and 32 GB of DDR4 RAM (computer A), using the R project [60]. Additionally, simulations were also performed on an Ubuntu server, equipped with 55 threads, 512 GB of RAM, and 1 TB SSD + 8 TB Intel HD storage (computer B). This study analysed a dataset comprising 6964 HIV-1 Group M sequences encompassing subtypes A, B, C, D, F1, G, H, and J (Fig. 2 (1)). The class distribution reflects the inherent imbalance in the Los Alamos National Laboratory (LANL) HIV Sequence Database: https://www.hiv.lanl.gov. Sequence lengths varied substantially, ranging from 86 to 10 414 bp (Fig. 2 (2)), a variability that would mislead alignment-based methods but is accommodated naturally by the fixed-dimension adjacency matrix representation. Scheme: (1) Number of sequences per HIV-1 subtype in the LANL dataset. Subtypes H and J reflect the limited availability of sequences in the database; the implications for classifier training due to class imbalance are discussed in the Results and Discussion section. (2) Sequence length distribution by HIV-1 subtype. Subtypes B and C contain predominantly near-complete genomes (∼10 000 bp), whereas subtypes A, H, and J show shorter sequences on average (< 2000 bp), likely reflecting sequencing biases in the LANL database. The fixed-dimension adjacency matrix representation accommodates this length heterogeneity without truncation or padding. (3) Dendrogram derived from hierarchical clustering of 1455 HIV-1 sequences based on Euclidean distances between adjacency matrices. Subtypes B (blue) and C (light green) form largely homogeneous clusters on the left, indicating conserved trinucleotide transition patterns. Subtypes H and J appear dispersed throughout the central region, reflecting higher structural heterogeneity. The 22 clusters identified by the CLUSTER_DENDROGRAM algorithm (homogeneity threshold θ = 0.7 for the clusters to identify the main characteristics of their respective sequences) are demarcated at the base of the dendrogram. (4) Subtypes that are dominant in more clusters indicate high heterogeneity across the clusters and obtain more features for their classification. Each sequence was converted into a graph, and its adjacency matrix representation was obtained. For the feature selection step, sequences from each subtype were randomly selected under the condition that they are longer than 800 bp; this threshold is motivated by established guidelines for HIV-1 phylogenetic analysis: although alignments of 300–500 nucleotides are generally sufficient to reconstruct subtype clades, longer fragments spanning complete or near-complete gene regions yield substantially more reliable classification, particularly for genomic regions under slower evolutionary pressure such as pol RT [61]. At 800 bp, sequences are likely to encompass at least one complete functional gene, providing a richer trinucleotide transition profile for the adjacency matrix representation. This length criterion maximizes the available genetic information per training sequence while excluding short, potentially incomplete or low-quality entries that could introduce noise into the clustering and feature selection steps. The dataset comprised 1455 sequences, including 200 for each subtype A, B, C, D, F1, G, and H, and 55 for subtype J (limited by the sequence length criterion). To avoid data leakage, these sequences were used only in the training set of the machine learning models applied later. The adjacency matrices of the selected sequences were compared pairwise using the distances indicated in Section 1.3. Given the 1455 sequences in the dataset, a symmetric distance matrix of order 1,455 × 1,455 was obtained. Ward’s hierarchical clustering method was applied to this matrix to reveal the intrinsic data structure producing the dendrogram. To illustrate this step, the dendrogram obtained using Euclidean distance is shown in Fig. 2, Panel (3). The dendrogram leaves were coloured according to their respective HIV subtypes. Subtypes C (light green) and B (blue) formed distinct, largely homogeneous clusters on the left of the dendrogram, indicating conserved structural patterns. In contrast, subtypes H and J were intermixed in the central region, reflecting higher intra-subtype heterogeneity. The 22 identified clusters varied in size and composition, demonstrating that within-subtype variation is sufficient to prevent simple global aggregation of all sequences from the same class. This heterogeneity underscores the importance of the proposed feature selection strategy. Clusters predominantly composed of sequences from the same class indicate high structural conservation, whereas small or mixed-composition clusters reflect divergence from canonical subtype profiles. Selecting k-mers that specifically capture the features of these heterogeneous clusters is essential for the classifier to reliably identify divergent or atypical sequences. Feature selection distribution Analysing k-mer occurrences within the identified clusters enables a targeted, quota-based feature selection for supervised learning. For each identified cluster, homogeneity with a class indicates that the k-mer choices within that cluster contribute to characterizing the dominant subtype. For example, using the dendrogram based on Euclidean distance [Fig. 2, Panel (3)], with the identification of 22 clusters. Figure 2, Panel (4) indicates the number of clusters in which each subtype is dominant. Subtypes A and H, which show high heterogeneity across the clusters, are dominant in more clusters (6 of 22 for subtype H and 5 of 22 for subtype A); this explains the larger number of selected features for these subtypes. Subtypes B and C, which are grouped into homogeneous clusters (one cluster each), have fewer selected features. Subtype J, although highly heterogeneous across clusters, is dominant in only one cluster and therefore has fewer features. The distribution of features by subtype is indicated for some values, yielding Table 1. Details the distribution of selected features per subtype across different total feature counts (n), which were subsequently used to evaluate model sensitivity to feature dimensionality. A comprehensive list of selected features and additional descriptions for n=256 is provided in Supplementary File S2. Table 1.Number of features (discriminative k-mers) allocated per HIV-1 subtype as a function of total feature count nFeatures (n)ABCDF1GHJ81111111120333322226414339961731282866181812355256551212363624701151211523237170461412310242304747140140942804620484659393280280186558193307269514014042042028083813940969301861865605593721117186 Number of features (discriminative k-mers) allocated per HIV-1 subtype as a function of total feature count n Results CAMELLIA was assessed through six complementary analyses: (1) distance measure for clustering, (2) sensitivity of classification accuracy to feature count, (3) comparison with PCA-based feature selection, (4) comparison with AF feature extraction methods, (5) benchmarking against AF tools with custom training capability (CASTOR-KRFE) and tools without training (COMET and REGA v3.47), and (6) runtime comparison against an alignment-based method (MEGA/MUSCLE) and FAMSA. The influence of distance on hierarchical clustering The training set comprised 1455 sequences (the same sequences used for feature selection). Subsequently, a 70/30 split was used for training and validation. The held-out test set consisted of 5509 HIV-1 sequences of variable lengths, encompassing all eight subtypes. The distances used for hierarchical clustering influenced the feature selection process, which was based on features from the input genomic sequences, yielding better classification results. In this simulation, the XGB method was used for ML, and the results were presented in Fig. 3. Heatmap of test accuracy across six distance metrics. Colour intensity encodes accuracy, ranging from light (≈ 0.92) to dark purple (≈0.96). Red borders indicate the peak accuracy for each distance metric. Euclidean and Jaccard distances achieve their highest accuracy at n = 1000 (0.9579 and 0.9602, respectively), suggesting that moderate feature sets are sufficient for these metrics. Clark and Bray distances peak at n = 3000 (0.9570 and 0.9597), while Frobenius reaches its maximum at n = 3800 (0.9548) and Hamming at n = 1600 (0.9512). Overall, Frobenius and Hamming distances yield consistently lower accuracy across all feature counts, whereas Jaccard, Bray, and Euclidean perform most competitively. Overall, the methods achieved an accuracy above 0.92 regardless of the number of selected features. The maximum accuracy was not achieved with all 4096 features, suggesting that an excessive number of features may introduce noise into the model. Impact of feature count on classification accuracy Using the same training/test dataset as in the previous simulation, the number of features may influence the method’s outcome. In this simulation, the clustering step was performed using the Euclidean distance, a commonly employed metric in the literature, which yielded accuracy results similar to those obtained with the other distance metrics evaluated. The number of features selected, ranging from 8 features (the number of subtypes) to 4096 features (the total number of possible k-mers), was chosen to analyse the effect of feature quantity on the classification performance of RF and XGB on the training and test sets, summarized in Table 2. Table 2.Classification accuracy on the training, validation, and test datasets as a function of feature count, using RF and XGB with CAMELLIA’s cluster-based feature selectionRF accuracyXGB accuracyFeaturesTrainValidationTestTrainValidationTest40961.00000.97990.95831.00000.99180.955930721.00000.97940.95591.00000.99240.947720481.00000.97320.94831.00000.98830.954110241.00000.97460.94571.00000.98210.96135121.00000.96080.94051.00000.97390.95152561.00000.95260.93081.00000.96700.94251281.00000.92440.90381.00000.94640.9258641.00000.89900.88911.00000.91830.8982201.00000.80420.80801.00000.80760.816880.99790.70860.72260.99930.80830.8123 Classification accuracy on the training, validation, and test datasets as a function of feature count, using RF and XGB with CAMELLIA’s cluster-based feature selection Training/Validation accuracies generally exceeded test accuracies, as expected given the test set’s greater heterogeneity and size. To isolate the influence of feature count on model performance, we consider validation set results, which comprise more homogeneous sequences and thus mitigate confounding factors such as sequence length. Both models showed similar performance, with the XGBoost method marginally higher in accuracy than the Random Forest method. This suggests that XGB is more effective at leveraging the sparse discriminative signals introduced by cluster-specific features (Fig. 4). Notably, using the full 4096-feature set resulted in a performance plateau or a marginal decline for XGB and RF, indicating that a subset of k-mer transitions carries minimal discriminative information. The analysis using the Gain metric of XGB feature importance and the unit invariant knee (UIK) method [62] suggests that model performance stabilizes at approximately n=234 features, representing the optimal accuracy dimensionality trade-off (Fig. 5). Classification accuracy of RF and XGB as a function of feature count. The inflexion point near n=128∼ 256 indicates the accuracy-dimensionality trade-off, with XGB consistently outperforming RF at higher feature counts. Gain metric for XGB feature importance on train dataset. The UIK method for knee-point detection indicates that 234 features are sufficient for the prediction model (accuracy = 0.9463). Notably, incorporating a larger number of features is unlikely to yield substantial benefits in model performance and may instead introduce distortion, as illustrated by the case n=4,096. Comparison with PCA-based feature selection To better investigate and assess the cluster-based feature selection, we analyse and compare it with PCA as an alternative dimensionality reduction strategy. Using the same feature count values (n), XGB models were trained on PCA-transformed feature vectors. Results are summarized in Table 3. Table 3.RF and XGB accuracy using PCA for dimensionality reduction. With the PCA method, the XGB model yielded comparable results. In comparison with the features selected by the CAMELLIA method, both models achieved higher accuracy on the test set, indicating that the features identified by CAMELLIA are more informative for sequence classificationRF accuracyXGB accuracyFeaturesTrainValidationTestTrainValidationTest40961.00000.98140.96041.00000.98620.946830721.00000.97540.95991.00000.99010.944320481.00000.97150.92921.00000.98230.947010241.00000.96270.92451.00000.97640.94955121.00000.95680.93471.00000.96660.94032561.00000.94890.90521.00000.95480.93141281.00000.90870.89821.00000.92530.9209641.00000.88610.87801.00000.90280.8920221.00000.79170.80161.00000.79860.809280.99710.70530.70120.97640.70130.6981 RF and XGB accuracy using PCA for dimensionality reduction. With the PCA method, the XGB model yielded comparable results. In comparison with the features selected by the CAMELLIA method, both models achieved higher accuracy on the test set, indicating that the features identified by CAMELLIA are more informative for sequence classification The comparison between PCA and CAMELLIA’s cluster-based feature selection reveals a nuanced picture that depends on both the classifier and the number of features. At intermediate dimensionality (n=128), PCA yields RF Test accuracy of 0.8982, and CAMELLIA’s cluster-based selection yields 0.9038, whereas XGB Test accuracy is 0.9209 for both models. The CAMELLIA strategy, at higher feature counts, achieves results comparable to PCA for both classifiers. PCA components are linear combinations of all 4096 k-mer transitions and cannot be traced back to specific sequence motifs or genomic coordinates, whereas CAMELLIA’s selected features retain their biological identity and can be mapped directly to functional regions of the HIV-1 genome. This interpretability gap represents a fundamental limitation of PCA-based approaches for applications requiring mechanistic insight beyond classification accuracy. As shown in Table 4, both methods generally achieve high performance across most subtypes, especially B, C, D, and G, with consistently strong values for sensitivity, specificity, precision, recall, F1-score, and balanced accuracy. In both cases, subtype A stands out as one of the weakest classes, with lower sensitivity and balanced accuracy than the others, indicating greater classification difficulty for this group. Subtype J, however, shows an even more pronounced limitation: CAMELLIA exhibits a markedly sharper drop in performance, with sensitivity of only 0.0138 and a balanced accuracy of 0.5068. This outcome likely stems from pronounced heterogeneity among subtype J sequences within their clusters, a consequence of the unfavourable sample size and sequence availability for this subtype relative to the others, which limits the cluster-based feature selection strategy’s ability to adequately capture its structural diversity. Table 4.Performance metrics by subtype for XGB models using CAMELLIA and PCA feature selection (128 features). CAMELLIA achieves higher sensitivity and balanced accuracy for subtypes A and H, the most challenging and underrepresented classes, while PCA yields marginally better results for subtypes D and G. Subtype J remains the most difficult class in both settings, with CAMELLIA showing a near-random balanced accuracy (0.5068) and sensitivity close to zero, whereas PCA retains comparatively higher, though still limited, performance for this subtypeCAMELLIA (XGB)PCA (XGB)SubtypeSensit.Specif.PrecisionRecallF1-scoreBal. Acc.Sensit.Specif.PrecisionRecallF1-scoreBal. Acc. A 0.83000.99240.94860.83000.88530.91120.68300.96500.91500.68300.78300.8240 B 1.00000.99320.96151.00000.98040.99660.98800.99700.99600.98800.99200.9930 C 0.99750.99870.99250.99750.99500.99810.99400.99901.00000.99400.99700.9970 D 0.94500.99530.97170.94500.95820.97020.97600.99700.98900.97600.98200.9870 F1 0.96380.99790.98720.96380.97530.98080.95500.98600.92700.95500.94100.9710 G 0.97000.99340.96160.97000.96580.98170.97800.99600.98200.97800.98000.9870 H 0.96450.94740.67660.96450.79530.95600.78500.97100.83400.78500.80900.8780 J 0.01380.99980.66670.01380.02700.50680.37000.99900.67600.37000.47900.6850 Performance metrics by subtype for XGB models using CAMELLIA and PCA feature selection (128 features). CAMELLIA achieves higher sensitivity and balanced accuracy for subtypes A and H, the most challenging and underrepresented classes, while PCA yields marginally better results for subtypes D and G. Subtype J remains the most difficult class in both settings, with CAMELLIA showing a near-random balanced accuracy (0.5068) and sensitivity close to zero, whereas PCA retains comparatively higher, though still limited, performance for this subtype AF feature extraction methods Using other AF methods for feature selection may affect the performance of ML methods. Based on the method developed in [30], simulations were performed with the FCGR, SWF, RTD, and KMER methods for feature selection and sequence classification using RF. Using 1455 HIV-1 sequences previously employed in the earlier simulations and fixing the k-mer size at k=6, it was observed that each method required virus-specific parameters for HIV-1, not specified in [30]. A total of 161 simulations were conducted, varying the parameters of each method; because each method defines a different set of tunable parameters (e.g. resolution mode for FCGR, word length and gap pattern for SWF, transition order for RTD, and k-mer length for KMER), the number of valid parameter combinations, and therefore the number of simulations, necessarily differs across methods and was not fixed to an equal value [30]. The FCGR method achieved the highest accuracy, as shown in Table 5. Table 5.Performance metrics by method. The means were calculated over 80 simulations for FCGR, 10 simulations for RTD, 11 simulations for KMER, and 60 simulations for SWF, reflecting the number of valid parameter combinations available for each method rather than an equal, pre-fixed simulation budgetMethodAccuracyMacro F1MCCFCGR 0.9476 ± 0.0175 0.8524 ± 0.0161 0.9400 ± 0.0201 RTD 0.9394 ± 0.0104 0.8403 ± 0.0117 0.9310 ± 0.0115 KMER 0.9520 ± 0.0068 0.8558 ± 0.0065 0.9449 ± 0.0079 SWF 0.2447 ± 0.0298 0.1772 ± 0.0361 0.1333 ± 0.0352 Performance metrics by method. The means were calculated over 80 simulations for FCGR, 10 simulations for RTD, 11 simulations for KMER, and 60 simulations for SWF, reflecting the number of valid parameter combinations available for each method rather than an equal, pre-fixed simulation budget Under these conditions, the FCGR method demonstrated the highest average accuracy, with performance approaching that of CAMELLIA. The highest accuracy (0.9571) was obtained with the FCGR mode using a resolution of 128. It is worth noting that simulations that varied parameters for each method incurred higher computational costs. The parameters evaluated in the simulations for each method are summarized in [30]. Benchmarking against other classification methods We benchmarked CAMELLIA against CASTOR-KRFE, a state-of-the-art AF method supporting custom model training. Both methods were evaluated under identical training and test splits using 10-fold cross-validation. For CAMELLIA, the XGBoost model was employed with n=256 features, a value close to that of the UIK method, thereby preserving model efficiency. CASTOR-KRFE was performed without a fixed k-mers count, as the method does not impose such a constraint. Table 6 presents per-subtype precision and F1-score. The results reveal an important nuance: CAMELLIA (XGB) achieves higher precision and F1 for the high-prevalence subtypes B, C and G. For subtype J, the most underrepresented class (, ), both methods exhibited markedly poor performance, with CAMELLIA achieving higher precision, but extremely low recall and F1-score for both approaches, indicating that both methods exhibited difficulty in classifying subtype J. Table 6.Per-subtype precision, recall, and F1-score for CAMELLIA (XGB, n=256) versus CASTOR-KRFE under identical training and test splits. CAMELLIA achieves higher precision for subtypes A, F1, G, and J, which present greater classification challenges in the analysed datasets; CASTOR-KRFE achieves higher scores for subtypes B, C, D, and H. The H and J subtypes demonstrate low scores across both methodologiesCAMELLIA (XGB)CASTOR-KRFESubtypeAccuracyPrecisionRecallF1-scoreAccuracyPrecisionRecallF1-score Macro 0.940 0.915 0.845 0.836 0.9340.8900.8450.842 A 0.903 ± 0.052 0.902 ± 0.025 0.901 ± 0.0186 0.842 ± 0.081 0.917 ± 0.031 0.873 ± 0.038 B 0.982 ± 0.006 0.998 ± 0.001 0.990 ± 0.003 0.992 ± 0.006 0.999 ± 0.003 0.995 ± 0.004 C 0.991 ± 0.004 0.998 ± 0.001 0.994 ± 0.002 0.994 ± 0.007 0.998 ± 0.004 0.997 ± 0.004 D 0.982 ± 0.004 0.979 ± 0.014 0.981 ± 0.008 0.986 ± 0.009 0.982 ± 0.009 0.986 ± 0.007 F1 0.989 ± 0.011 0.969 ± 0.005 0.979 ± 0.005 0.984 ± 0.007 0.974 ± 0.011 0.979 ± 0.007 G 0.983 ± 0.007 0.974 ± 0.006 0.978 ± 0.006 0.969 ± 0.014 0.958 ± 0.009 0.964 ± 0.011 H 0.721 ± 0.022 0.903 ± 0.067 0.800 ± 0.023 0.785 ± 0.067 0.854 ± 0.111 0.810 ± 0.042 J 0.767 ± 0.266 0.034 ± 0.028 0.065 ± 0.050 0.571 ± 0.143 0.081 ± 0.038 0.135 ± 0.057 Per-subtype precision, recall, and F1-score for CAMELLIA (XGB, n=256) versus CASTOR-KRFE under identical training and test splits. CAMELLIA achieves higher precision for subtypes A, F1, G, and J, which present greater classification challenges in the analysed datasets; CASTOR-KRFE achieves higher scores for subtypes B, C, D, and H. The H and J subtypes demonstrate low scores across both methodologies In another approach, using tools that support model training on user-specific datasets offers greater specificity for the classes under investigation. Pre-trained tools such as COMET and REGA v3.47 are designed for a broader set of subtypes (140 and 40, respectively, including CRFs), which increases the risk of misclassification when the target dataset contains only a subset of those classes. COMET achieved a test accuracy of 0.7508, and REGA v3.47 achieved 0.7223. Per-subtype precision and F1-scores for these tools span a larger class space, resulting in lower overall accuracy on the eight-subtype test set. Although these methods offer an online interface and classify several subtypes, including CRFs, for the analysis of specific subtypes, methods that allow training with custom sequences (CAMELLIA and CASTOR-KRFE) are more efficient for classification. Comparison with an alignment-based method: (MEGA/MUSCLE) and FAMSA Alignment-based methods are traditionally regarded as highly accurate for closely related sequences, but their computational cost limits scalability. We benchmarked CAMELLIA against MEGA X (version 10.2) using the MUSCLE multiple sequence alignment algorithm as the preprocessing step. MEGA/MUSCLE achieved an accuracy of 0.9723 on the test set, requiring approximately 80 640 s (≈22 h) of processing. CAMELLIA processed the same dataset in 20 s with a test accuracy of 0.9425 (XGB), representing an ∼4,032-fold reduction in runtime with a < 5% absolute reduction in accuracy. This trade-off demonstrates CAMELLIA as the practical choice for real-time genomic surveillance and large-scale database analyses in which multiple sequence alignment is computationally prohibitive. FAMSA (Fast and Accurate Multiple Sequence Alignment) is a progressive alignment algorithm specifically designed to efficiently align large protein families containing thousands to hundreds of thousands of sequences [20]. In the assessment, processing the same dataset took 1020 s (13 min). CAMELLIA reduced the runtime by ∼51-fold to generate the alignment, demonstrating substantial computational efficiency compared to conventional alignment algorithms. Additionally, FAMSA provides a guide-tree structure that can be utilized for further phylogenetic analyses; however, such downstream analyses were not conducted within the scope of the present investigation. Explainability and genomic mapping CAMELLIA method is built directly on the k-mer composition of the input sequences. Feature selection based on k-mers with the highest frequencies within given clusters or classes captures sequence-level characteristics that are informative for model training and subsequent subtype prediction. The individual contribution to the classification model can be assessed using the Gain metric of XGBoost feature importance. For example, for n=256 features used in the previous simulations, Fig. 6 presents the ten features with the highest Gain values, indicating the k-mers that contributed most to classification. Top 10 feature importance (Gain-XGB) on train model with n=256 features. Feature CAGACA exhibits the highest XGBoost gain (0.0801), emerging as the most discriminative marker, selected for subtype C classification. A more granular perspective on feature relevance can be obtained through SHAP (SHapley Additive exPlanations) values, which decompose the model output into per-feature contributions for each prediction. The SHAP beeswarm plot shows one horizontal line per feature, with each point representing a dataset observation. The point’s position on the x-axis indicates that feature’s SHAP value for the corresponding sample: points to the right of zero indicate that the feature increases the prediction (i.e. supports the predicted class), whereas points to the left indicate the opposite effect. The colour of each point encodes the actual feature value, purple for low values (e.g. a rare or absent k-mer) and yellow for high values (a frequent k-mer), making it immediately apparent whether the presence or absence of the k-mer is more influential for the model. Features whose points are more widely dispersed along the horizontal axis exhibit greater variability in their impact across samples, whereas features concentrated near zero contribute little to the predictions. The vertical ordering of features follows their global importance: the feature at the top has the highest mean absolute SHAP value, indicating the largest average impact on predictions across the entire dataset. Figure 7 presents the ten features that most influenced classification within each subtype class. This analysis not only reveals that distinct k-mers drive discrimination across different subtypes but also quantifies whether each feature exerts a positive or negative effect on the classification decision, providing a richer characterization of model behaviour than aggregate importance metrics alone. SHAP values per subtype on train model with n=256 features. The visualization reveals distinct patterns of feature importance across HIV subtypes. Subtypes B, C, and D demonstrate strong discriminative power through high feature importance (orange/yellow colouring), indicating robust positive SHAP contributions to correct classification. Conversely, subtypes A, H, and J rely predominantly on low feature importance (purple colouring), suggesting these subtypes are characterized by the absence of certain discriminative features rather than their presence. On average, k-mers enriched in adenine were prevalent across all HIV-1 subtypes. Specifically, the patterns AAAGAA, AAAAAT, AAGAAA, and AGAAAA appeared at consistently high frequencies, consistent with the known A-rich nucleotide composition of lentiviral genomes and specific structural motifs [63]. Conversely, CG-rich k-mers such as CCGCGT and CGTACG showed comparatively low occurrence, reflecting CpG dinucleotide suppression in HIV-1 as a mechanism to evade host antiviral defence mediated by the Zinc finger Antiviral Protein (ZAP) [64]. CAMELLIA method also provides the positions of k-mers within sequences as an additional resource for understanding the influence of these k-mers on sequence behaviour (e.g. the region to which the k-mer belongs and nucleotide repetitions). To illustrate the positional analysis of sequence features, Table 7 displays the first five genomic coordinates occupied by the k-mer AAAGAA within the subtype B reference sequence B.JP.-.DR1777.AB604948. Table 7.Positional mapping of the selected feature AAAGAA within the HIV-1 subtype B reference sequence B.JP.-.DR1777.AB604948 (GenBank accession AB604948). Coordinates are 1-based nucleotide positions. The five occurrences shown represent the first five instancesFeature (k-mer)Sequence accessionSubtypeStart (bp)End (bp)Seq. length (bp)AAAGAAB.JP.-.DR1777.AB604948B2432489915AAAGAAB.JP.-.DR1777.AB604948B139113969915AAAGAAB.JP.-.DR1777.AB604948B165516609915AAAGAAB.JP.-.DR1777.AB604948B194419499915AAAGAAB.JP.-.DR1777.AB604948B273927449915 Positional mapping of the selected feature AAAGAA within the HIV-1 subtype B reference sequence B.JP.-.DR1777.AB604948 (GenBank accession AB604948). Coordinates are 1-based nucleotide positions. The five occurrences shown represent the first five instances For this reference sequence, the genomic locations of all AAAGAA occurrences were mapped to the major structural elements of the HIV-1 genome (Fig. 8). Genomic localization of the k-mer AAAGAA across the HIV-1 subtype B reference sequence B.JP.-.DR1777.AB604948 (GenBank AB604948). Each marker indicates a position where the k-mer occurs. Genomic regions annotated include LTR, gag, pol, vif, vpr, tat, rev, vpu, env, and nef. The distribution of AAAGAA across multiple functional regions is consistent with its non-specific A-rich composition. In general, subtypes A, H, and J exhibited a larger proportion of selected k-mers with zero occurrence across their sequences. This pattern is likely influenced by the shorter average sequence lengths in these subtypes (Fig. 2), which reduce the probability of observing any given trinucleotide transition. Discussion Figure 9 summarizes the processing time for all methods evaluated in this study, ranging from 14 to 80,640 s when classifying with 5509 sequences (same sequence dataset). For feature extraction methods, the reported time corresponds to the mean processing time across all simulations. Despite their fast execution, the large number of simulations required to explore parameter variations substantially increases the total computational cost of these methods. Alignment-based methods (FAMSA and MEGA) exhibited considerably longer processing times than AF approaches. For analysing processing time, the COMET, REGA, and MEGA methods were run on Computer A, with COMET and REGA being fully online-interface methods, and MEGA offering its own free software interface. Simulations with the CAMELLIA, CASTOR-KRFE, and FAMSA methods were run on Computer B due to its greater processing and memory capacity. The computer configurations are described in Section 2.4. Alignment-based methods (FAMSA and MEGA) exhibit the longest processing times. REGA and COMET require more processing time compared to the CAMELLIA and CASTOR-KRFE methods. These latter two methods prove to be considerably faster, primarily because model training and classification are completed within seconds. Another relevant property concerns model training strategy: methods that support user-provided training sequences demonstrated higher classification accuracy than pre-trained tools, which rely on fixed internal reference sets that may introduce misclassification due to the broader range of variants represented in their training data, and also demonstrated substantially reduced computational cost. A notable limitation of the present study concerns subtypes H and J, which are substantially underrepresented in the LANL database relative to the other six subtypes (n=764 and n=200, respectively, compared with n=1,000 for subtypes A, B, C, D, F1, and G). This imbalance propagated through all stages of CAMELLIA: the clustering phase produced smaller and more heterogeneous clusters for these subtypes (Figs 2-4), the quota-based feature selection allocated a disproportionately large share of features to H and J in an attempt to compensate (Table 1), and the classifier nevertheless yielded markedly lower precision and F1-scores for both subtypes (Table 6). These results reflect the inherent difficulty of learning robust decision boundaries from scarce training examples rather than a fundamental limitation of the AF representation itself. Addressing this challenge remains an important direction for future work, including evaluating class-balancing strategies or cost-sensitive learning, as well as developing specialized sequence-encoding tools that capture the fine-grained structural characteristics of divergent and underrepresented subtypes more effectively. The evaluated tools differed significantly in design philosophy and practical applicability. CAMELLIA is particularly suited for comprehensive analyses requiring simultaneous processing of complete sequence datasets with user-defined training, enabling superior performance for specific research questions. AF machine-learning-based approaches such as CAMELLIA generally achieve higher classification accuracy than pre-trained tools by adapting to the characteristics of the target population. COMET and REGA v3.47, while prioritizing accessibility through web interfaces, impose constraints on batch size and do not support custom retraining. A critical consideration for all tools is their dependence on curated training sets. For rapidly mutating viruses such as HIV-1, Hepatitis C virus (HCV), and influenza, these training sets require frequent updates to maintain classification accuracy as new variants emerge. CAMELLIA’s capacity for custom retraining from any labelled sequence dataset is particularly valuable in this context. When subtype-specific patterns are of interest or when recently characterized sequences are available, retraining CAMELLIA using curated datasets from repositories such as GenBank/NCBI or the LANL HIV database is strongly recommended. The increasing volumes of sequence data generated by modern high-throughput sequencing platforms further underscore the importance of AF. CAMELLIA offers substantial computational advantages in processing speed and scalability, providing a favourable trade-off between accuracy and cost compared with alignment-based methods. Conclusion This study presents CAMELLIA, an alignment-free method for genomic classification. It is based on a graph representation of the sequences that uses a combination of unsupervised and supervised learning algorithms to identify and preserve signals from underrepresented subgroups within each class, thus, achieving the feature selection that extracts informative k-mers of the sequences. CAMELLIA’s value proposition extends beyond achieving accuracy comparable to that of alignment-based methods at a lower computational cost. The results presented here indicate that the proposed method offers specific and measurable advantages in scenarios where alignment-based approaches are fundamentally limited. The method shows similarly effective performance across variations of the feature selection methods, when compared with approaches such as PCA and other AF feature extraction methods. This is also observed across variations in the distance metric used in the hierarchical clustering step. For highly divergent or recombinant sequences, such as HIV genomes, multiple sequence alignment assumes common positional homology across all inputs, whereas CAMELLIA’s graph-based representation captures local k-mer patterns without requiring homologous positions, making it intrinsically robust to recombination breakpoints. In large-scale real-time genomic surveillance settings, the ∼4032-fold runtime advantage over MEGA/MUSCLE (20 s versus 80 640 s on 5509 sequences) and ∼35-fold runtime advantage over FAMSA (14 s versus 1020 s on 5509 sequences) becomes operationally decisive: at the scale of tens of thousands of new sequences per day, alignment-based pipelines are infeasible, whereas CAMELLIA scales linearly with sequence count. For sequences of highly variable or incomplete length, common in clinical sequencing, where partial genomes, amplicon sequences, and low-coverage assemblies predominate, the fixed-dimension adjacency matrix naturally accommodates variable-length inputs without truncation or imputation. For emerging or non-model organisms lacking curated reference alignments, CAMELLIA requires only a labelled FASTA file for training, with no prior alignment infrastructure. Finally, for user-defined classification problems that do not map to established subtype systems, such as classifying sequences by geographic clade, drug-resistance phenotype, or host species, CAMELLIA’s user-trainable architecture offers greater flexibility than pre-trained tools such as COMET and REGA. In summary, CAMELLIA presents a scalable, interpretable, and adaptable method, particularly suited for scenarios at the intersection of data volume, sequence diversity, and the need for custom, rapidly updatable classifiers applicable beyond HIV-1 to any labelled genomic dataset. CAMELLIA is freely available at https://github.com/tatianasaita/CAMELLIA, including user instructions, data, and scripts that allow complete replication of the study. Key points Scalable AF classification: CAMELLIA achieves accurate genomic sequence subtyping without multiple sequence alignment, reducing runtime by ∼4032-fold (20 s) on an eight-subtype HIV-1 dataset of 5509 sequences while retaining 94 % test accuracy. Scalable AF classification: CAMELLIA achieves accurate genomic sequence subtyping without multiple sequence alignment, reducing runtime by ∼4032-fold (20 s) on an eight-subtype HIV-1 dataset of 5509 sequences while retaining 94 % test accuracy. Novel cluster-aware feature selection: The quota-based feature selection algorithm stratifies k-mer selection by dendrogram-defined cluster, ensuring representation of divergent minority sequence groups that global ranking methods overlook, a design that is novel among AF classification pipelines. Novel cluster-aware feature selection: The quota-based feature selection algorithm stratifies k-mer selection by dendrogram-defined cluster, ensuring representation of divergent minority sequence groups that global ranking methods overlook, a design that is novel among AF classification pipelines. Competitive benchmarking: CAMELLIA (XGB) outperforms COMET (0.75) and REGA v3.47 (0.72) in overall accuracy and matches CASTOR-KRFE (0.934) globally, while offering a unique combination of cluster-aware feature selection, biological interpretability, and user-trainable classification unavailable in any single competing tool. Competitive benchmarking: CAMELLIA (XGB) outperforms COMET (0.75) and REGA v3.47 (0.72) in overall accuracy and matches CASTOR-KRFE (0.934) globally, while offering a unique combination of cluster-aware feature selection, biological interpretability, and user-trainable classification unavailable in any single competing tool. Defined use cases with absolute advantage: CAMELLIA is specifically advantageous for (i) highly divergent/recombinant sequences, (ii) large-scale real-time surveillance, (iii) variable-length or incomplete sequences, (iv) emerging pathogens without established references, and (v) user-defined classification problems outside standard subtype systems. Defined use cases with absolute advantage: CAMELLIA is specifically advantageous for (i) highly divergent/recombinant sequences, (ii) large-scale real-time surveillance, (iii) variable-length or incomplete sequences, (iv) emerging pathogens without established references, and (v) user-defined classification problems outside standard subtype systems. Interpretable genomic mapping: Selected k-mers are traceable to specific genomic positions and annotatable against functional regions (LTR, gag, pol, env, etc.), enabling downstream biological hypothesis generation, a capability absent from most AF classifiers. Interpretable genomic mapping: Selected k-mers are traceable to specific genomic positions and annotatable against functional regions (LTR, gag, pol, env, etc.), enabling downstream biological hypothesis generation, a capability absent from most AF classifiers. General applicability: CAMELLIA accepts any labelled sequence dataset in standard FASTA format and is not restricted to HIV, viral, or even microbial sequences. General applicability: CAMELLIA accepts any labelled sequence dataset in standard FASTA format and is not restricted to HIV, viral, or even microbial sequences. Supplementary Material Acknowledgments A.T.L.Q. is a senior investigator and CNPq Research Fellow. Special thanks to Sr. Vinicius Soares Costa for their valuable contribution to the scientific illustrations. Author contributions: Tatiana Mari Saita (Conceptualization [equal], Data curation [equal], Formal analysis [equal], Investigation [equal], Methodology [equal], Resources [equal], Software [equal], Supervision [equal], Validation [equal], Visualization [equal], Writing—original draft [lead], Writing—review & editing [equal]), Matheus Henrique Pimenta-Zanon (Data curation [equal], Investigation [equal], Software [equal], Validation [equal], Visualization [equal], Writing—review & editing [equal]), Artur Trancoso Lopo de Queiroz (Conceptualization [equal], Data curation [equal], Formal analysis [equal], Investigation [equal], Methodology [equal], Validation [equal], Visualization [equal], Writing—review & editing [equal]), Glaucia Maria Bressan (Conceptualization [equal], Data curation [equal], Formal analysis [equal], Investigation [equal], Methodology [equal], Validation [equal], Visualization [equal], Writing—review & editing [equal]), and Fabricio Martins Lopes (Conceptualization [equal], Data curation [equal], Formal analysis [equal], Methodology [equal], Resources [equal], Software [equal], Validation [equal], Visualization [equal], Writing—review & editing [equal]). Contributor Information Tatiana Mari Saita, Associated Graduate Program in Bioinformatics (PPGAB), Universidade Tecnológica Federal do Paraná (UTFPR), Alberto Carazzai, 1640, Cornélio Procópio, 86300-000, Paraná, Brasil. Matheus Henrique Pimenta-Zanon, Associated Graduate Program in Bioinformatics (PPGAB), Universidade Tecnológica Federal do Paraná (UTFPR), Alberto Carazzai, 1640, Cornélio Procópio, 86300-000, Paraná, Brasil; Departamento de Genética Escola Superior de Agricultura ‘Luiz de Queiroz’, Universidade de São Paulo, Pádua Dias Av., 11, 13418-900, São Paulo, Brasil. Artur Trancoso Lopo de Queiroz, Laboratório de Pesquisas Clínicas e Translacionais, Instituto Gonçalo Moniz, Fundação Oswaldo Cruz (FIOCRUZ), Rua Waldemar Falcão, 121, Salvador, 40296-710, Bahia, Brasil. Glaucia Maria Bressan, Associated Graduate Program in Bioinformatics (PPGAB), Universidade Tecnológica Federal do Paraná (UTFPR), Alberto Carazzai, 1640, Cornélio Procópio, 86300-000, Paraná, Brasil. Fabricio Martins Lopes, Associated Graduate Program in Bioinformatics (PPGAB), Universidade Tecnológica Federal do Paraná (UTFPR), Alberto Carazzai, 1640, Cornélio Procópio, 86300-000, Paraná, Brasil. Supplementary data Supplementary data is available at NAR Genomics & Bioinformatics online. Conflict of interest No competing interests are declared. Funding This study was financed by the Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)—Finance Code 001, Fundação Araucária (grant numbers 035/2019 and 138/2021, and NAPI—Bioinformática), and CNPq (grant numbers 440412/2022-6 and 408312/2023-8). This study was supported by FAPESP for M.H.P-Z. (grant number 2025/10318-5). Data availability CAMELLIA is implemented in R and is freely available under the MIT license at https://github.com/tatianasaita/CAMELLIA. The exact version of the software used to generate the results presented in this article has been archived on Zenodo and is available at https://doi.org/10.5281/zenodo.21366715. An updated version of the software, incorporating subsequent improvements, is also archived and available at https://doi.org/10.5281/zenodo.21366714. All HIV-1 sequences analysed in this study are publicly accessible via the Los Alamos National Laboratory HIV Sequence Database: https://www.hiv.lanl.gov/content/sequence/HIV/mainpage.html. References Associated Data Supplementary Materials Data Availability Statement CAMELLIA is implemented in R and is freely available under the MIT license at https://github.com/tatianasaita/CAMELLIA. The exact version of the software used to generate the results presented in this article has been archived on Zenodo and is available at https://doi.org/10.5281/zenodo.21366715. An updated version of the software, incorporating subsequent improvements, is also archived and available at https://doi.org/10.5281/zenodo.21366714. All HIV-1 sequences analysed in this study are publicly accessible via the Los Alamos National Laboratory HIV Sequence Database: https://www.hiv.lanl.gov/content/sequence/HIV/mainpage.html.