Revealing the Shape of Genome Space via K K -mer Topology

Yuta Hozumi and Guo-Wei Wei · 2024

Read Revealing the Shape of Genome Space via K K -mer Topology by Yuta Hozumi and Guo-Wei Wei (2024) 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-2412-20202.txt.

Description

Abstract Despite decades of effort, understanding the shape of genome space in biology remains a challenge due to the similarity, variability, diversity, and plasticity of evolutionary relationships among species, genes, or other biological entities. We present a k k -mer topology method, the first of its kind, to delineate the shape of the genome space.

Catalog record

CREATORYuta Hozumi and Guo-Wei Wei
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE85 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-20202

Browse the full library · About the Tower of Babel

Full text

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

Revealing the Shape of Genome Space via K K -mer Topology Yuta Hozumi and Guo-Wei Wei Abstract Despite decades of effort, understanding the shape of genome space in biology remains a challenge due to the similarity, variability, diversity, and plasticity of evolutionary relationships among species, genes, or other biological entities. We present a k k -mer topology method, the first of its kind, to delineate the shape of the genome space. K K -mer topology examines the topological persistence and the evolution of the homotopic shape of the sequences of k k nucleotides in species, organisms, and genes using persistent Laplacians, a new multiscale combinatorial approach. We also propose a topological genetic distance between species by their topological invariants and non-harmonic spectra over scales. This new metric defines the topological phylogenetic trees of genomes, facilitating species classification and clustering. K K -mer topology substantially outperforms state-of-the-art methods on a variety of benchmark datasets, including mammalian mitochondrial genomes, Rhinovirus, SARS-CoV-2 variants, Ebola virus, Hepatitis E virus, Influenza hemagglutinin genes, and whole bacterial genomes. K K -mer topology reveals the intrinsic shapes of the genome space and can be directly applied to the rational design of viral vaccines. keywords: Shape of genome space, Phylogenetic analysis, Topological genetic distance, Persistent Laplacian 1 Introduction Phylogenetic analysis of genetic sequences is vital for understanding evolutionary relationships among species and within species [ 1 , 2 ] . Genetic sequences can be regarded as sequences of letters, that is, four letters for nucleotides and 20 letters for amino acids. Comparison of sequences can be challenging due to nonuniform lengths, mutations, and sequencing and/or assembly errors. In particular, in full-genome comparisons, different species often have dramatically varying lengths, making it challenging to define genetic metrics between sequences. Therefore, having a robust and reliable method to extract meaningful features that encode complex patterns and capture the shape of the genome space is essential and challenging. Traditional phylogenetic analysis relies on ‘sequence alignment’ using multiple sequence alignment (MSA) tools such as Clustal Omega [ 3 ] , MAFFT [ 4 ] , and MUSCLE [ 5 ] . Alignment-based methods are effective for identifying mutations in sequences [ 6 , 7 , 8 , 9 , 10 ] . However, these methods may fail when conserved segments are not properly aligned or have different lengths, a common challenge with real-world data. Additionally, alignment-based methods are time-intensive and memory-demanding, making large-scale sequence comparisons difficult. Alternatively, ‘alignment-free methods’ transform variable-length sequences into uniform objects, such as vectors, for sequence analysis [ 11 ] . This approach enables the effective comparison of sequences regardless of sequence lengths [ 12 ] . Moreover, because alignment-free methods extract features from individual sequences, their computational complexity scales only with the sequence length and the number of sequences [ 13 ] . This makes whole-genome comparisons across species more efficient and easily parallelizable [ 14 , 15 , 16 , 17 ] . Numerous alignment-free methods have been proposed, primarily categorized as word frequency- and information theory-based methods. The former includes k -mer methods [ 18 ] , where the frequency of words or motifs is counted and concatenated into a vector. Subsequently, the similarity or difference between sequences can be computed using a vector-based distance metric. Several extensions have been proposed to enhance efficiency and distance calculation [ 19 , 20 , 21 , 22 , 16 ] . In information theory-based methods, the distance between sequences is estimated by the amount of shared information between the two sequences using entropy and/ or complexity measures such as Kolmogorov complexity [ 23 ] , Lempel-Ziv complexity [ 24 ] , Shannon entropy [ 25 ] , etc. Comprehensive overviews of these methods can be found in [ 12 , 26 , 13 ] . However, these methods do not incorporate positional information from nucleotides. Several advanced alignment-free methods have also been proposed. Among them, the natural vector method (NVM) analyzes the moments of the k -mer positions [ 27 , 28 ] . The chaos game representation (CGR) [ 29 ] represents the sequence as an iterative function, which can be visualized as an image [ 30 ] . Various generations of CGR have been proposed [ 31 , 32 , 33 , 34 ] . In addition, other methods such as the discrete Fourier power spectrum method [ 35 , 36 ] , fuzzy integral similarity method [ 37 ] , and others [ 38 ] have been developed for phylogenetic analysis. Persistent homology is an algebraic topology tool for analyzing the shape of complex data [ 39 ] . Chan et al. [ 40 ] utilized persistent homology to compute sequence dissimilarity in viruses. The 0th-order homology and the 1st-order homology corresponded to vertical and horizontal evolution, respectively. This approach was used in analyzing the evolution of SARS-CoV-2 through the topological recurrence index (tRI) [ 9 ] . Nguyen et al. [ 41 ] applied persistent homology to the CGR of viral sequences. However, persistent homology neglects the intrinsic biological characteristics of genetic sequences. To overcome the limitation of persistent homology, persistent topological Laplacians (PTLs), including persistent combinatorial Laplacian or persistent spectral graph for point cloud data [ 42 ] and persistent Hodge Laplacian for data on manifolds [ 43 ] were introduced. By tracking the changes in the harmonic and non-harmonic spectra of a series of PTLs induced by filtration, one can uncover the topological and geometrical shape of the data. Specifically, the multiplicity of the harmonic spectra, i.e., the zero-eigenvalues, gives the Betti number of persistent homology at appropriate topological dimensions, while the non-harmonic spectra reveal the homotopic shape evolution. In this work, we introduce the k -mer topology, a novel topological approach for sequence analysis. K -mer topology extracts the topological persistence of k -mer segments in a genome through persistent homology and/ or persistent Laplacian, the latter further captures the evolution of the homotopic shape of k -mers during filtration. We also define a novel topological genetic distance to define phylogenetic trees and position individual species, organisms, or genes in the genome space. To benchmark the proposed method, we consider both classification tasks and phylogenetic analysis. Our method significantly outperforms other competing methods in viral classification and whole-genome phylogenetic analysis. The proposed topological genetic distance not only sheds light on genome evolution, but also provides a reliable antigenetic distance for the rational design of viral vaccines. 2 Results 2.1 Overview of K -mer topology Figure 1: Workflow of k -mer topology. From a query sequence, k-mers are extracted. The positions of individual k-mers are used to compute the k-mer specific distances. Using these distances, persistent Laplacian computes the persistent spectra of k -mers The harmonic persistent spectrum of the persistent Laplacian provides the persistent Betti numbers, which represent the number of connected k -mer components across multiple scales, while the non-harmonic persistent spectrum yields the homotopic shape evolution of the k -mers over scales. These features are converted into a genome topological vector. Topological genetic distances are defined between genome topological vectors for genome classification and/or phylogenetic analysis. The workflow of the k -mer topology is depicted in Figure 1 1 1 1 Illustration from NIAID NIH BIOART Source #64,

Read the complete text