Biology subjects

Alanko, J.

Publications and source records attributed to Alanko, J..

13 recordsLinked to original sources

bioRxiv2026

Fast Set Operations for Compact k-mer Sets

The k-mer spectrum of a set of sequences is the set of k-length substrings the sequences contain. This lossy representation of sequence content pervades modern genomics. Recently, the spectral Burrows-Wheeler transform (SBWT) has emerged as a space-efficient representation of k-spectra that also supports efficient k-mer lookup queries and, more generally, easy navigation of the de Bruijn graph of the k-spectrum. In this paper, we examine primitive set operations, such as intersection, union, and set difference, on SBWT-encoded k-spectra and show that these operations can be supported efficiently. Moreover, efficient merging leads directly to a new memory-efficient algorithm for SBWT construction, which was able to build the SBWT for the 661K bacterial dataset containing 88 billion distinct k-mers in 50 hours using 186 GiB of RAM and 112 GiB of disk space. Given the pervasiveness of k-mer sets in genomics and the continued rapid growth of genomic databases, our work opens the door to a wide array of future applications that manipulate and reason about genomic data by dealing directly with simultaneously compact and searchable k-mer set representations offered by the SBWT. 2012 ACM Subject ClassificationTheory of computation [->] Design and analysis of algorithms Digital Object Identifier10.4230/LIPIcs.WABI.2026. Supplementary MaterialSoftware (Source Code): https://github.com/LoreDepuydt/sbwt-set-operations FundingThis work has benefited from funding from the French State under the France 2030 program, reference ANR-21-IDES-0006. The European Metropolis of Lille and the University of Lille are also acknowledged for their funding and support of the project WILL-CHAIRES-25-001-BOSSA.

bioinformatics↗

bioRxiv2025

CD74 regulates antitumor immunity in melanoma by reprogramming dendritic cell immunogenicity and migration

Metastatic cutaneous melanoma remains a major therapeutic challenge, as many patients fail to respond or relapse following immune checkpoint therapy. The function of CD74, originally described as an MHC-II chaperone and receptor for macrophage migration inhibitory factor, remains poorly understood in tumor immunity. In this study, we show that systemic CD74 deletion in a syngeneic melanoma model significantly delayed tumor growth and reshaped the tumor immune microenvironment, and synergized with immune checkpoint blockade. Tumors in Cd74-/- mice had more effector and memory CD8+ T cells producing IFN-{gamma} and granzyme B than in control mice. Loss of CD74 promoted expansion of migratory cDC1s with elevated MHC-I and CCR7 expression. Cd74-/- professional antigen presenting cells increased cross-priming capacity for tumor-derived antigens in vivo and in vitro. Absence of CD74 induced the expression of CCR7, a key lymph node homing molecule, on cDCs and enhanced their ability to migrate towards the CCL19 ligand in single cell tracking analyses. These findings identify CD74 as a regulator of dendritic cell function and a promising therapeutic target to improve melanoma immunogenicity. One Sentence SummaryCD74 restrains cross-priming and migration capacity of dendritic cells, leading to impaired CD8+ T-cell infiltration and activation in tumor immunity.

immunology↗

bioRxiv2024

Self-generated chemotaxis of mixed cell populations

Cell and tissue movement in development, cancer invasion, and immune response relies on chemical or mechanical guidance cues. In many systems, this behavior is locally guided by self-generated signaling gradients rather than long-range, pre-patterned cues. However, how heterogeneous mixtures of cells interact non-reciprocally and navigate through self-generated gradients remains largely unexplored. Here we introduce a theoretical framework for the self-organized chemotaxis of heterogeneous cell populations. We find that relative chemotactic sensitivity of cell populations controls their long-time coupling and co-migration dynamics, with boundary conditions such as external cell- and attractant reservoirs substantially influencing the migration patterns. We further predict an optimal parameter regime that leads to robust and colocalized migration. We test our theoretical predictions with in vitro experiments demonstrating the co-migration of different immune cell populations, and quantitatively reproduce observed migration patterns under wild-type and perturbed conditions. Interestingly, immune cell co-migration appears close to the predicted optimal regime. Finally, we incorporate mechanical interactions into our framework, revealing a phase diagram that illustrates non-trivial interplays between chemotactic and mechanical non-reciprocity in driving collective migration. Together, our findings suggest that self-generated chemotaxis is a robust strategy for emergent multicellular navigation.

biophysics↗

bioRxiv2023

Scalable De Novo Classification of Antibiotic Resistance of Mycobacterium Tuberculosis

We develop a robust machine learning classifier using both linear and nonlinear models (i.e., LASSO logistic regression (LR) and random forests (RF)) to predict the phenotypic resistance of Mycobacterium tuberculosis (MTB) for a broad range of antibiotic drugs. We use data from the CRyPTIC consortium to train our classifier, which consists of whole genome sequencing and antibiotic susceptibility testing (AST) phenotypic data for 13 different antibiotics. To train our model, we assemble the sequence data into genomic contigs, identify all unique 31-mers in the set of contigs, and build a feature matrix M, where M [i, j] is equal to the number of times the i-th 31-mer occurs in the j-th genome. Due to the size of this feature matrix (over 350 million unique 31-mers), we build and use a sparse matrix representation. Our method, which we refer to as MTB++, leverages compact data structures and iterative methods to allow for the screening of all the 31-mers in the development of both LASSO LR and RF. MTB++ is able to achieve high discrimination (F-1 greater than 80%) for the first-line antibiotics. Moreover, MTB++ had the highest F-1 score in all but three classes and was the most comprehensive since it had a F-1 score greater than 75% in all but four (rare) antibiotic drugs. We use our feature selection to contextualize the 31-mers that are used for the prediction of phenotypic resistance, leading to some insights about sequence similarity to genes in MEGARes. Lastly, we give an estimate of the amount of data that is needed in order to provide accurate predictions.

bioinformatics↗

bioRxiv2023

Unveiling the ultrastructural landscape of native extracellular matrix via lift-out cryo-FIBSEM and cryo-ET

The extracellular matrix (ECM) is a highly hydrated, three-dimensional network composed of various macromolecules and signaling factors. It serves as a structural scaffold for cells and plays an essential role in the regulation of numerous cellular processes, including cell migration, adhesion, and proliferation. Despite its importance in metazoans, structural knowledge is rudimentary on how the components of the matrisome are secreted, remodeled, and interact with each other and with surrounding cells. Specifically, the exact molecular assembly of important ECM fibers, such as fibronectin fibrils, fibrillin microfibrils, or Collagen-VI filaments has remained enigmatic. This is largely due to methodological limitations in specimen preparation for conventional room-temperature electron microscopy (EM). To overcome these limitations, we have developed a cell culture-based 3D-ECM platform compatible with sample thinning by cryo-lift out focused ion beam (FIB) milling and cryo-electron tomography (cryo-ET). Our workflow involves the implementation of cell-derived matrices (CDMs) grown on EM grids, resulting in a highly adaptable and versatile tool to closely mimic ECM environments. This allows us to visualize native ECM and its components for the first time in their fully hydrated, cellular context. Our data reveals an intricate network of ECM fibers and their positioning with respect to matrix-secreting cells. In addition to D-spaced collagen fibers, we visualize previously unresolved fibrous structures, and an amorphous matrix co-assembling in proximity to ECM fibers and delineating the boundary between ECM and empty extra-cellular space. Intra- and extracellular granules presumably represent assembly intermediates of the ECM. Our results add to the structural atlas of the ECM and provide novel insights into ECM secretion, assembly and maintenance.

cell biology↗

bioRxiv2022

Sinking the way: a dual role for CCR7 in collective leukocyte migration

Immune responses crucially rely on the rapid and coordinated locomotion of leukocytes. While it is well established that single-cell migration is often guided by gradients of chemokines and other chemoattractants, it remains poorly understood how such gradients are generated, maintained and modulated. Combining experiment and theory on leukocyte chemotaxis guided by the G protein-coupled receptor (GPCR) CCR7, we demonstrate that in addition to its role as the sensory receptor that steers migration, CCR7 also acts as a generator and modulator of chemotactic gradients. Upon exposure to the CCR7 ligand CCL19, dendritic cells (DCs) effectively internalize the receptor and ligand as part of the canonical GPCR-desensitization response. We show that CCR7 internalization also acts as an effective sink for the chemoattractant, thereby dynamically shaping the spatio-temporal distribution of the chemokine. This mechanism drives complex collective migration patterns, enabling DCs to create or sharpen chemotactic gradients. We further show that these self-generated gradients can sustain the long-range guidance of DCs, adapt collective migration patterns to the size and geometry of the environment, as well as provide a guidance cue for other co-migrating cells. Such dual role of CCR7 as a GPCR that both senses and consumes its ligand can thus provide a novel mode of cellular self-organization.

cell biology↗

bioRxiv2021

Matchtigs: minimum plain text representation of kmer sets

We propose a polynomial algorithm computing a minimum plain-text representation of kmer sets, as well as an efficient near-minimum greedy heuristic. When compressing read sets of large model organisms or bacterial pangenomes, with only a minor runtime increase, we shrink the representation by up to 60% over unitigs and 27% over previous work. Additionally, the number of strings is decreased by up to 97% over unitigs and 91% over previous work. Finally, a small representation has advantages in downstream applications, as it speeds up SSHash-Lite queries by up to 4.26x over unitigs and 2.10x over previous work. Availabilitymatchtigs: https://github.com/algbio/matchtigs SSHash-Lite: https://github.com/jermp/sshash-lite

bioinformatics↗

bioRxiv2021

Syotti: Scalable Bait Design for DNA Enrichment

Bait-enriched sequencing is a relatively new sequencing protocol that is becoming increasingly ubiquitous as it has been shown to successfully amplify regions of interest in metagenomic samples. In this method, a set of synthetic probes ("baits") are designed, manufactured, and applied to fragmented metagenomic DNA. The probes bind to the fragmented DNA and any unbound DNA is rinsed away, leaving the bound fragments to be amplified for sequencing. This effectively enriches the DNA for which the probes were designed. Most recently, Metsky et al. (Nature Biotech 2019) demonstrated that bait-enrichment is capable of detecting a large number of human viral pathogens within metagenomic samples. In this work, we formalize the problem of designing baits by defining the Minimum Bait Cover problem, which aims to find the smallest possible set of bait sequences that cover every position of a set of reference sequences under an approximate matching model. We show that the problem is NP-hard, and that it remains NP-hard under very restrictive assumptions. This indicates that no polynomial-time exact algorithm exists for the problem, and that the problem is intractable even for small and deceptively simple inputs. In light of this, we design an efficient heuristic that takes advantage of succinct data structures. We refer to our method as syotti. The running time of syotti shows linear scaling in practice, running at least an order of magnitude faster than state-of-the-art methods, including the recent method of Metsky et al. At the same time, our method produces bait sets that are smaller than the ones produced by the competing methods, while also leaving fewer positions uncovered. Lastly, we show that syotti requires only 25 minutes to design baits for a dataset comprised of 3 billion nucleotides from 1000 related bacterial substrains, whereas the method of Metsky et al. shows clearly super-linear running time and fails to process even a subset of 8% of the data in 24 hours. Our implementation is publicly available at https://github.com/jnalanko/syotti.

bioinformatics↗

bioRxiv2021

Buffering Updates Enables Efficient Dynamic de Bruijn Graphs

MotivationThe de Bruijn graph has become a ubiquitous graph model for biological data ever since its initial introduction in the late 1990s. It has been used for a variety of purposes including genome assembly (Zerbino and Birney, 2008; Bankevich et al., 2012; Peng et al., 2012), variant detection (Alipanahi et al., 2020b; Iqbal et al., 2012), and storage of assembled genomes (Chikhi et al., 2016). For this reason, there have been over a dozen methods for building and representing the de Bruijn graph and its variants in a space and time efficient manner. ResultsWith the exception of a few data structures (Muggli et al., 2019; Holley and Melsted, 2020; Crawford et al., 2018), compressed and compact de Bruijn graphs do not allow for the graph to be efficiently updated, meaning that data can be be added or deleted. The most recent compressed dynamic de Bruijn graph (Alipanahi et al., 2020a), relies on dynamic bit vectors which are slow in theory and practice. To address this shortcoming, we present a compressed dynamic de Bruijn graph that removes the necessity of dynamic bit vectors by buffering data that should be added or removed from the graph. We implement our method, which we refer to as BufBOSS, and compare its performance to Bifrost, DynamicBOSS, and FDBG. Our experiments demonstrate that BufBOSS achieves attractive trade-offs compared to other tools in terms of time, memory and disk, and has the best deletion performance by an order of magnitude. Contactalanko.jarno@gmail.com

bioinformatics↗

bioRxiv2020

Genomic Epidemiology with Mixed Samples

Genomic epidemiology is a tool for tracing transmission of pathogens based on whole-genome sequencing. We introduce the mGEMS pipeline for genomic epidemiology with plate sweeps representing mixed samples of a target pathogen, skipping the colony pick step. The pipeline includes the novel mGEMS read binner for probabilistic assignments of sequencing reads, and the scalable pseudoaligner Themisto. We demonstrate the effectiveness of our approach using closely related samples in a nosocomial setting, obtaining results that are comparable to those based on colony picks. Our results lend firm support to more widespread consideration of genomic epidemiology with mixed infection samples.

bioinformatics↗

bioRxiv2018

A framework for space-efficient variable-order Markov models

MotivationMarkov models with contexts of variable length are widely used in bioinformatics for representing sets of sequences with similar biological properties. When models contain many long contexts, existing implementations are either unable to handle genome-scale training datasets within typical memory budgets, or they are optimized for specific model variants and are thus inflexible.\n\nResultsWe provide practical, versatile representations of variable-order Markov models and of interpolated Markov models, that support a large number of context-selection criteria, scoring functions, probability smoothing methods, and interpolations, and that take up to 4 times less space than previous implementations based on the suffix array, regardless of the number and length of contexts, and up to 10 times less space than previous trie-based representations, or more, while matching the size of related, state-of-the-art data structures from Natural Language Processing. We describe how to further compress our indexes to a quantity related to the redundancy of the training data, saving up to 90% of their space on repetitive datasets, and making them become up to 60 times smaller than previous implementations based on the suffix array. Finally, we show how to exploit constraints on the length and frequency of contexts to further shrink our compressed indexes to half of their size or more, achieving data structures that are 100 times smaller than previous implementations based on the suffix array, or more. This allows variable-order Markov models to be trained on bigger datasets and with longer contexts on the same hardware, thus possibly enabling new applications.\n\nAvailability and implementationhttps://github.com/jnalanko/VOMM

bioinformatics↗

bioRxiv2018

GGA2 and RAB13 regulate activity-dependent β1-integrin recycling

{beta}1-integrins mediate cell-matrix interactions and their trafficking is important in the dynamic regulation of cell adhesion, migration and malignant processes like cancer cell invasion. Here we employ an RNAi screen to characterize regulators of integrin traffic and identify the association of Golgi-localized gamma ear-containing Arf-binding protein 2 (GGA2) with {beta}1-integrin and its role in recycling of the active but not inactive {beta}1-integrin receptors. Silencing of GGA2 limits active {beta}1-integrin levels in focal adhesions and decreases cancer cell migration and invasion congruent with its ability to regulate the dynamics of active integrins. Using the proximity-dependent biotin identification (BioID) method, we identify two RAB family small GTPases, RAB13 and RAB10, associating with GGA2 and {beta}1-integrin. Functionally, RAB13 silencing triggers the intracellular accumulation of active {beta}1-integrin, reduces integrin activity, in focal adhesions, and cell migration, similarly to GGA2 depletion, indicating that both facilitate active {beta}1-integrin recycling the plasma membrane. Thus, GGA2 and RAB13 are important specificity determinants for integrin activity-dependent traffic.

cell biology↗

bioRxiv2017

ProLIF: a quantitative assay for investigating integrin cytoplasmic protein interactions and synergistic membrane effects on proteoliposomes

Integrin transmembrane heterodimeric receptors control a wide range of biological interactions by triggering the assembly of large multiprotein complexes at their cytoplasmic interface. A diverse set of methods have been used to investigate cytoplasmic interactions between integrins and intracellular proteins. These predominantly consist of peptide-based pull-downs and biochemical immuno-isolations from detergent-solubilized cell lysates. However, quantitative methods to probe integrin-protein interactions in a more biologically relevant context where the integrin is embedded within a lipid bilayer have been lacking. Here we describe a technique called ProLIF (Protein-Liposome Iinenteractions by Flow cytometry) to reconstitute recombinant integrin transmembrane domain (TMD) and cytoplasmic tail (CT) fragments on liposomes as individual or {beta} subunits or as {beta} heterodimers and, using flow cytometry, to rapidly and quantitatively measure protein interactions with these membrane-embedded integrins. Importantly, the assay can analyse binding of fluorescent proteins directly from cell lysates without further purification steps. By combining integrins with membrane lipids to generate proteoliposomes, the effects of membrane composition such as PI(4,5)P2 presence on protein recruitment to the integrin CTs can be analyzed. ProLIF requires no specific instrumentation, apart from a standard flow cytometer and can be applied to measure a broad range of membrane-dependent protein-protein interactions with the potential for high-throughput/multiplex analyses.

molecular biology↗