GraphPart: Homology partitioning for biological sequence analysis

Felix Teufel, Magnús Halldór Gíslason, José Juan Almagro Armenteros, Alexander Rosenberg Johansen, Ole Winther, Henrik Nielsen

Abstract

When splitting biological sequence data for the development and testing of predictive models, it is necessary to avoid too closely related pairs of sequences ending up in different partitions. If this is ignored, performance estimates of prediction methods will tend to be exaggerated. Several algorithms have been proposed for homology reduction, where sequences are removed until no too closely related pairs remain. We present GraphPart, an algorithm for homology partitioning, where as many sequences as possible are kept in the dataset, but partitions are defined such that closely related sequences always end up in the same partition. Evaluation of GraphPart on Protein, DNA and RNA datasets shows that it is capable of retaining a larger number of sequences per dataset, while providing homology separation quality on par with reduction approaches.

Introduction

In biological machine learning, the standard practice of random data splitting often fails due to evolutionary relationships between sequences, known as homology. If a training set contains a sequence highly similar to one in the test set, the model may simply memorize features rather than learning generalizable biological rules. This leads to inflated performance metrics that do not hold up on novel data.

Traditionally, researchers have used "homology reduction"—deleting sequences until no two are overly similar. However, this discards significant amounts of valuable data. GraphPart introduces "homology partitioning," which groups similar sequences into the same folds, allowing researchers to retain more data while maintaining a strict firewall against redundancy.

Methods: The GraphPart Workflow

GraphPart utilizes a graph-based clustering approach to manage sequence similarity. The process follows four primary steps:

  1. Graph Construction: Pairwise identities are calculated between all sequences using global alignments (Needleman-Wunsch) or faster approximations (MMseqs2). Sequences are represented as nodes, with edges connecting those exceeding a similarity threshold.
  2. Restricted Clustering: A modified single-linkage clustering groups sequences. Merges are restricted to prevent clusters from becoming too large or unbalancing class labels.
  3. Partition Assignment: Clusters are assigned to folds (e.g., for k-fold cross-validation) to maintain balance in sequence count and label distribution.
  4. Heuristic Removal: Any remaining "illegal" edges between partitions are resolved by iteratively moving or removing the minimum number of sequences required to break the links.
The four-step GraphPart workflow: graph initialization, restricted clustering, partition assignment, and final refinement.

Datasets and Benchmarking

The authors evaluated GraphPart across a diverse set of biological data types, including Protein (e.g., NetSurfP 2.0), DNA (e.g., DeePromoter), and RNA (e.g., nRC). These datasets vary in sequence length, class distribution, and conservation levels, providing a robust test for the algorithm's versatility.

Overview of the DNA, RNA, and Protein datasets used to evaluate GraphPart's performance.

Key Results

GraphPart demonstrates significant advantages over traditional reduction methods:

  • Data Retention: GraphPart consistently retains more sequences—up to 50% more in certain protein datasets—compared to reduction-based tools like CD-HIT.
  • Separation Quality: By utilizing global alignments, GraphPart achieves near-perfect separation, eliminating "leaky" similarities across folds that often plague local-alignment-based tools.
  • Robustness: The algorithm maintains high performance even with truncated sequences or short motifs, where other methods often struggle to identify homology.

Discussion and Limitations

While powerful, GraphPart's all-vs-all alignment approach introduces $O(N^2)$ computational complexity. While manageable for datasets of ~30,000 sequences, scaling to millions of sequences requires faster backends like MMseqs2. Additionally, at extremely low identity thresholds, the high connectivity of the sequence graph can lead to excessive sequence removal during the final heuristic step. Future work focuses on integrating faster alignment approximations and embedding-based similarities to enhance scalability.

Summary updated

Abstract

Abstract When splitting biological sequence data for the development and testing of predictive models, it is necessary to avoid too closely related pairs of sequences ending up in different partitions. If this is ignored, performance estimates of prediction methods will tend to be exaggerated. Several algorithms have been proposed for homology reduction, where sequences are removed until no too closely related pairs remain. We present GraphPart, an algorithm for homology partitioning, where as many sequences as possible are kept in the dataset, but partitions are defined such that closely related sequences always end up in the same partition. Evaluation of GraphPart on Protein, DNA and RNA datasets shows that it is capable of retaining a larger number of sequences per dataset, while providing homology separation quality on par with reduction approaches.
BibTeX
@inproceedings{teufel2023graphpart,
  author = {Felix Teufel and Magnús Halldór Gíslason and José Juan Almagro Armenteros and Alexander Rosenberg Johansen and Ole Winther and Henrik Nielsen},
  title = {{GraphPart: Homology partitioning for biological sequence analysis}},
  booktitle = {NAR},
  year = {2023},
  doi = {10.1093/nargab/lqad088},
}
Figure