A Graph-based Approach to Variant Description Extraction from Sequences

Mark A. Santcroos, Walter A. Kosters, Mihai Lefter, Jeroen F.J. Laros, Jonathan K. Vis · 2025

Read A Graph-based Approach to Variant Description Extraction from Sequences by Mark A. Santcroos, Walter A. Kosters, Mihai Lefter, Jeroen F.J. Laros, Jonathan K. Vis (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-18472.txt.

Introduction

Mark Santcroos and co-authors present a 2025 graph method for naming genetic variants from DNA sequences. Exact variant names matter for sharing results in genomics. Complex variants, like several insertions and deletions at once, strain direct naming. Their method builds a graph from all smallest alignments of the change. That graph holds the full picture of the variant in one structure. Three ways to read a name back out of the graph are offered.

One reader produces names in the standard HGVS system used by clinics. Tests compared their names with the main public variant database. For simple variants, the names matched exactly. For complex ones, their names carried more meaning than the database entries. The authors argue a graph view beats a single flat description. The tools aim at labs that must report hard variants cleanly.

Catalog record

CREATORMark A. Santcroos, Walter A. Kosters, Mihai Lefter, Jeroen F.J. Laros, Jonathan K. Vis
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE86 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-18472

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Graph-based Approach to Variant Description Extraction from Sequences Mark A. Santcroos, Walter A. Kosters, Mihai Lefter, Jeroen F.J. Laros, Jonathan K. Vis Abstract Accurate variant descriptions are of paramount importance in the field of genomics. The domain is confronted with increasingly complex variants, e.g., combinations of multiple indels, making it challenging to generate proper variant descriptions directly from chromosomal sequences. We present a graph based on all minimal alignments that is a complete representation of a variant, which gives insight into the nature of a variant compared to a single variant description. We provide three complementary extraction methods to derive variant descriptions from this graph, including one that yields domain-specific constructs from the HGVS nomenclature. Our experiments show that our methods in comparison with dbSNP, the authoritative variant database from the NCBI, result in identical HGVS descriptions for simple variants and more meaningful descriptions for complex variants, in particular for repeat expansions and contractions. \pgfsyspdfmark pgfid2742420000 \pgfsyspdfmark pgfid304242 \pgfsyspdfmark pgfid324242 \pgfsyspdfmark pgfid3742420000 1 Introduction Insights into a person’s DNA are of relevance for a wide range of applications, not limited to clinical and research settings. Sequencing is the process to obtain the genetic sequence from DNA. Typically, this results in segments of chromosomes that need to be aligned to a reference genome, e.g., Genome Reference Consortium Human Build 38 (GRCh38) for human samples, in order to reconstruct the individual’s complete chromosomal sequences. Because the human genome is large (circa 3\cdot 10^{9} nucleotides), and the individual differences between two genomes are relatively small (circa 0.6\% [ 1 ] ), it is practical to only look at the differences. These differences are called genetic variants. In practice, these are recorded by most variant calling tools in the Variant Call Format (VCF) [ 8 ] . Variants appear in various formats in clinical communication, scientific literature, and are also stored in databases. The effectiveness of this information exchange largely depends on the specific format and quality of how these variants are described [ 6 , 4 ] . The Human Genome Variation Society (HGVS) Variant Nomenclature Committee [ 9 ] publishes recommendations [ 11 ] for HGVS variant descriptions, that are intended to be human-readable, but provides no guidelines on how to construct them from sequences. A standardization effort with a machine-readable focus is the Variant Representation Specification (VRS) [ 26 ] . SPDI features a single replacement notation (Sequence, Position, Deletion, Insertion) and employs the Variant Overprecision Correction Algorithm (VOCA) for normalization. The Single Nucleotide Polymorphism Database (dbSNP) [ 21 ] is a public archive for genetic variation made available by National Center for Biotechnology Information (NCBI). The widespread usage of the dbSNP database makes their specific choice in formatting of HGVS variants quite prevalent. In [ 31 ] , significant inconsistencies in variant descriptions across tools and databases are observed, noting that it specifically hinders automatic lookup. Often variant description languages define a normalization procedure to select one universally accepted description from a set of possibilities. Beyond normalization, in [ 20 ] the authors also discuss many other challenges to effectively curate variants from literature. The authors of [ 2 ] show that searching for a single description in PubMed does not retrieve all relevant articles for a variant. In a more clinical study [ 18 ] the authors observe that differences in nomenclature can “hide clinically relevant information in plain sight”. Challenges with VCF normalization have been addressed in [ 3 , unified ] . In [ 29 ] the authors observe that in repetitive genomic regions, different descriptions of the same deletions can lead to the same result. A sequence-based normalization method specifically for concise HGVS descriptions is discussed in [ 25 ] . The problem of choosing an accurate variant description and assisting the user with variant normalization has given rise to many platforms [ 10 , 17 , 16 , 28 ] . In the remainder of this paper we focus on a formal approach to calculate variant descriptions. Central is the problem of computing the distance between two strings and obtaining a series of edit operations [ 27 ] . Instead of focusing on one series of edit operations, we consider all minimal alignments corresponding to the simple edit distance [ 24 ] to generate variant descriptions. We introduce a new type of graph that is constructed from all these minimal alignments; a simplified example visualization using HGVS notation is shown in Figure 1 . Based on the structure of this graph, we provide three complementary methods to derive variant descriptions. We experimentally assess the effectiveness of our method by comparing our results to the HGVS descriptions in dbSNP. Finally, we discuss the broader implications of our methods and provide forward-looking statements. 1_2insTT 2C>T 3C>T 3del 3_4insT 5G>T 5del 5G>T 7_8insT 8_9insT Figure 1: A graph containing all LCS alignments for the strings ACCTGACT and ATCTTACTT . The paths through the graph correspond with six HGVS descriptions. The highlighted path with the description [2C>T;5G>T;8_9insT] corresponds to the HGVS recommendations. 2 Algorithms and Data Structures We start with preliminary definitions that we build upon later. Let \Sigma be a non-empty finite alphabet of symbols , e.g., \Sigma=\{\texttt{A},\texttt{C},\texttt{G},\texttt{T}\} , and S a finite string over \Sigma . The length of string S , written as |S| , is the number of symbols in S . The empty string (without any symbols, also said with length 0 ) is denoted as \varepsilon . We refer to the symbol at position i of S as S_{i} , with 0\leq i<|S| . We use the natural extension of this notation to refer to substrings of S , i.e., S_{i\ldots j} is the string containing the contiguous symbols S_{i},\ldots,S_{j-1} , with 0\leq i\leq j\leq|S| . Note that S_{i\ldots i}=\varepsilon . String U is a subsequence of string S if U=\varepsilon or there exists a sequence of integers i_{1},\ldots,i_{|U|} such that 0\leq i_{1}<\ldots<i_{|U|}<|S| and U=S_{i_{1}}\ldots S_{i_{|U|}} . To describe differences between two strings R (called reference sequence) and O (called observed sequence) we introduce the replacement (also known as substitution) operator i\!:\!j\,/\,S , with 0\leq i\leq j\leq|R| and S a substring of O that replaces the symbols R_{i}\ldots R_{j-1} with the string S . When i=j , the string S is inserted immediately before (the symbol on) the i -th position. We denote the empty replacement as \lambda . The string R can be transformed into O by applying a series of replacement operations. A longest common subsequence (LCS) for two strings R and O is a longest string U such that U is a subsequence of both R and O . In general, many of such LCSs exist for a given R and O . Often, only the length of the LCSs is of interest. The classic approach to calculate the (length of the) LCSs is to solve the well-known recurrence relation using dynamic programming to fill a table row by row [ 27 ] . 2.1 All LCS Alignments We are interested in finding all LCS alignments for a pair of highly similar strings. It is well-known [ 5 ] that LCS alignment is related to calculating the simple edit distance , e.g., [ 24 ] . For only calculating

Read the complete text