Biology subjects

Chandra, G.

Publications and source records attributed to Chandra, G..

At least 19 recordsLinked to original sources

bioRxiv2026

A conserved NLR activation switch governs global transcriptional control of antibiotic biosynthesis in Streptomyces

Nucleotide-binding and oligomerization domain-like receptors (NLRs) are conserved molecular switches that regulate innate immunity across diverse domains of life. While best known for their roles in immunity, bacterial NLR-related proteins also govern non-immune processes. In Streptomyces, the global transcriptional regulator AfsR employs an NLR-type architecture to control antibiotic production. Here, we identify a conserved histidine-aspartic acid motif within the nucleotide-binding and oligomerization domain of AfsR that functions as a universal NLR activation switch. Site-directed mutagenesis of this motif decouples AfsR from native upstream signals, locking it into a constitutive, autoactive "ON" state. Using integrated transcriptomics, ChIP-seq, and in vitro DNA-binding assays, we demonstrate that autoactivation expands the regulatory reach of AfsR via enhanced promoter affinity, directly controlling its canonical target afsS and uncovering wblH as an additional member of the AfsR regulon. Untargeted metabolomics further shows that autoactive AfsR drives systemic reprogramming of specialized metabolism, increasing the production of known antibiotics and awakening silent biosynthetic gene clusters in Streptomyces coelicolor and Streptomyces peucetius. Furthermore, phylogenomic analysis reveals that Actinomycetes encode multiple AfsR-like regulators with undefined roles in biosynthetic gene cluster regulation, suggesting a substantial reservoir of unexplored regulatory diversity that could be harnessed to expand natural product discovery. Together, our work provides fundamental insights into the functional diversity of NLRs and a framework for rationally engineering these regulators to unlock untapped microbial chemical diversity.

microbiology↗

bioRxiv2026

TrbA binds and locks a sliding clamp KorB to repress transcription on multi-drug resistance plasmids

Precise regulation of gene expression is essential for all living systems. Genes encoded on mobile genetic elements such as conjugative plasmids are also highly regulated to ensure stable inheritance, successful horizontal transfer, and adaptation to diverse bacterial hosts. The multi-drug resistance plasmid RK2 encodes an intricate regulatory network centred on the ParB-CTPase family protein KorB, which functions in both plasmid segregation and global gene regulation. We recently showed that KorB acts as a CTP-dependent DNA-sliding clamp that can be converted into a transcriptional repressor through direct interaction with the DNA-binding protein KorA. This clamp sliding-and-locking mechanism by KorAB enables highly effective transcriptional repression. Here, we investigate whether a third transcriptional regulator on the RK2 plasmid, TrbA, operates through a similar mechanism. Using a combination of structural prediction, biochemistry and in vivo transcriptional assays, we provide evidence that TrbA also directly interacts with KorB and functions as a clamp-locking factor. This KorB-TrbA interaction is mediated by a conserved aromatic interface that enables strong cooperative transcriptional repression. Disruption of this interface abolishes synergy, indicating that direct protein-protein interaction underpins KorB-TrbA cooperativity. Finally, bioinformatic analysis of a large plasmid database reveal that the tripartite KorB-KorA-TrbA system is present on numerous plasmids. Together, our findings establish TrbA as a bona fide KorB co-repressor and demonstrate how a single sliding clamp protein can integrate multiple partners to evolve a complex transcriptional regulatory network. IMPORTANCEPrecise regulation of gene expression ensures gene products are produced at the right time and in the right amounts. Recent works uncovered a new mechanism of bacterial gene regulation based on a clamp sliding and locking in a multi-drug resistance plasmid, RK2. KorB functions as a CTP-dependent DNA-sliding clamp capable of traveling over a long genomic distance. Sliding KorB is captured and locked in place by a partner protein, KorA, forming a stable complex at target promoters to repress transcription. Here, we show that another RK2 regulator, TrbA, also use this clamp sliding-locking mechanism, and identify an aromatic interface enabling TrbA-KorB-mediated transcriptional repression. Our findings show how a single sliding clamp integrates multiple partners to build a complex transcriptional regulatory network.

microbiology↗

bioRxiv2026

Defining the OrrA regulon and its role in development and antibiotic production in Streptomyces venezuelae NRRL B-65442

2.Streptomyces bacteria have complex life cycles involving hyphal growth, sporulation, and the production of diverse specialised metabolites, including antibiotics. In this study, we investigated the role of the highly conserved orphan response regulator OrrA in Streptomyces venezuelae NRRL B-65442. We show that S. venezuelae {Delta}orrA mutants are defective in sporulation and, using ChIP-seq, identify five OrrA binding sites in vivo. Tandem-mass-tag proteomics revealed that OrrA directly activates two of these putative target genes, wblA and vnz_04640, a finding consistent with previous work on OrrA in the distantly related S. coelicolor. We also demonstrate that deleting wblA blocks sporulation and that overexpressing wblA restores sporulation in the {Delta}orrA mutant. Additionally, chloramphenicol biosynthesis is upregulated in both the {Delta}orrA and {Delta}wblA mutants compared with the wild type. Taken together, these results indicate that the primary function of OrrA is to regulate WblA production, and that reduced intracellular WblA levels underlie the phenotypes observed in the {Delta}orrA mutant. 3. Data summaryThe authors confirm all supporting data, code and protocols have been provided within the article, through supplementary data files and via public databases.

microbiology↗

bioRxiv2026

Regulatory divergence and functional diversification of a c-di-GMP-controlled sigma factor in Actinomycetota

Members of the {sigma}28 family of alternative {sigma} factors typically regulate genes involved in flagellar biosynthesis. However, the only member of the {sigma}28 family present in the actinobacterial genus Streptomyces, WhiG, controls the differentiation of aerial hyphae into spores. WhiG activity is regulated by the second messenger c-di-GMP, which arms its cognate anti-{sigma}, RsiG, to bind and sequester the {sigma} factor. Understanding WhiG evolution can thus shed light on the diversity of processes regulated by c-di-GMP across Phylum Actinomycetota. Members of Actinomycetota comprise highly diverse filamentous and unicellular, flagellated and non-flagellated species, and the actinobacterial ancestor is predicted to have been motile. Here, our systematic analysis reveals that WhiG homologs are broadly distributed throughout the Actinomycetota and form two distinct clades: WhiG1, whose members have retained the ancestral association with the flagellar biosynthesis cluster and are not regulated by an RsiG anti-{sigma}, and WhiG2, whose members are typically regulated by RsiG via c-di-GMP. Bioinformatic analysis of their target regulons suggests that this {sigma} factor has significantly diversified in function to control various processes, including motility, chemotaxis, Type IV pili synthesis, sporulation, antibiotic biosynthesis, and c-di-GMP metabolism across diverse actinobacterial species. These findings highlight a phylogenetic split in the regulation and function of this key transcription factor throughout the phylum. ImportanceMounting global responses to dynamic environmental conditions is a crucial function that bacterial cells must perform. Global regulatory networks are most often studied in individual species, however, understanding how regulatory networks have evolved in distinct bacterial lineages remains an outstanding question. The alternative factor WhiG, which is found in the actinobacterial genus Streptomyces, is a dedicated sporulation , yet has long been known to have a close evolutionary relationship to factors that are responsible for regulation of flagellar biosynthesis. Analysis of the distribution of WhiG in Phylum Actinomycetota reveals that homologs typically co-occur with either a flagellar cluster or the c-di-GMP-binding anti- RsiG. Functional predictions of WhiG target genes across the Actinomycetota further reveal that diverse biological processes are controlled by these transcription factors, most notably motility, chemotaxis, Type IV pili biosynthesis, regulation of gene expression, c-di-GMP metabolism, and specialized metabolite biosynthesis.

microbiology↗

bioRxiv2025

A Novel Stress Response Pathway Mediates Antibiotic Tolerance and Architecture in Pseudomonas aeruginosa Biofilms

Pseudomonas aeruginosa is a multidrug-resistant opportunistic pathogen, with chronic infections often associated with biofilm formation. Here, we investigate the previously uncharacterized gene PA3049, which is upregulated under biofilm conditions, to determine its role in infection, biofilm formation, and antimicrobial tolerance. We show that the small uncharacterised protein PA3049, renamed as Biofilm antibiotic tolerance Regulator (BatR), promotes biofilm establishment and enhances bacterial survival in sub-inhibitory concentrations of antibiotics. Proteomic analysis revealed that BatR influences the R2/F2 pyocin cluster, which drives explosive cell lysis and extracellular DNA (eDNA) release during biofilm development. We further identify a specific interaction between BatR and PA0486 (SrkA), an uncharacterised Ser/Thr protein kinase. We show that SrkA controls biofilm and pyocyanin production, and lysis-mediated eDNA release through regulation of the R2/F2 pyocin cluster and activation of bacteriophage Pf1. Our findings support a model in which SrkA directly regulates key biofilm-associated phenotypes, while BatR acts as a modulatory partner that tunes SrkA activity under specific conditions. Finally, BatR function was tested in high- validity infection models, including the ex vivo pig lung model of cystic fibrosis infection and a synthetic chronic-wound model. In these models, BatR contributes to biofilm architecture and antibiotic tolerance, and modulates pyocyanin production. Our study implicates the BatR/SrkA system in the response of P. aeruginosa biofilms to antibiotic challenge in lung infections.

microbiology↗

bioRxiv2025

Stable inheritance of the Streptomyces linear plasmid SCP1 by dual ParABS partition systems

Low-copy-number plasmids often rely on dedicated maintenance mechanisms, such as partitioning systems, to ensure stable inheritance across generations. These partition systems actively segregate sister plasmid copies during cell division and are classified by the NTPase types they encode. While the distribution and organization of partition system types are well characterized in Enterobacteriaceae plasmids, their functions and diversity across broader bacterial taxa remain poorly understood. Here, we analyze a large and diverse plasmid database to examine the distribution of partition system types and find that plasmids encoding multiple partition systems are more common than previously recognized. Notably, many plasmids encode multiple partition systems of the same type, an organization that has not been previously investigated. To further investigate, we employ the Streptomyces linear plasmid SCP1, which encodes two type I ATP- and CTP-dependent parABS partition systems, as a model. Sequence analysis shows that both SCP1-encoded ParBs harbor less conserved CTPase domains than their chromosomal counterparts, suggesting they might diverge from canonical ParB functions. However, using chromatin immunoprecipitation with deep sequencing, biochemical assays, and targeted mutagenesis, we demonstrate that both proteins are bona fide ParB CTPase proteins: they recognize distinct parS sites on SCP1, bind and hydrolyze CTP, and slide to accumulate on DNA. Despite both systems being functional, only parABS1, but not parABS2, is crucial for SCP1 maintenance under standard laboratory conditions. Altogether, these findings provide the first functional characterization of dual ParB-CTPase partition systems coexisting on a single plasmid, advancing our understanding of plasmid maintenance in Streptomyces, and reveal new aspects of the diversity and distribution of plasmid partition systems in bacteria.

microbiology↗

bioRxiv2025

Haplotype-resolved diploid genome inference on pangenome graphs

Recent algorithmic advancements have shown how to utilize pangenome graphs in combination with the haplotype reconstruction framework of Li and Stephens to accurately reconstruct a haplotype from a reference pangenome graph and a set of input reads. However, significant work remains in developing techniques that utilize a pangenome graph to obtain a pair of phased haplotypes called a diploid pair. ResultsWe introduce new problem formulations and scalable algorithms for inferring phased diploid genomes from a pangenome graph and a set of input reads. We implement them in our tool DipGenie. The key idea is to jointly optimize genotyping and phasing along global paths through the pangenome graph, guided by a biologically motivated recombination budget that constrains inferred haplotypes to plausible mosaics of reference haplotypes. We evaluate DipGenie on real Illumina short-read data from the highly polymorphic MHC region in 22 leave-one-out diploid experiments, benchmarking against three tools that also operate on graph structures: VG, which samples haplotypes directly from the pangenome graph, and PanGenie + Beagle and Paragraph + Beagle, which derive local graphs from a VCF panel for per-site genotyping and delegate phasing to a statistical method. At full coverage, DipGenie achieves a geometric mean switch error rate (SER) of 0.86%, which is 5.7x lower than PanGenie + Beagle (4.88%), 7.9x lower than VG (6.77%), and 13.2x lower than Paragraph + Beagle (11.35%). For structural variant calling, DipGenie leads with a geometric mean F1-score of 0.571, compared to 0.470 (PanGenie + Beagle), 0.450 (VG), and 0.379 (Paragraph + Beagle). These advantages hold at every coverage level tested. Availability and Implementationhttps://github.com/gsc74/DipGenie.

bioinformatics↗

bioRxiv2025

Influence of simplifications on FE modelling of mandible and TMJ implants

End-stage temporomandibular joint (TMJ) disorders often necessitate joint replacement to restore bilateral mastication. Patient-specific TMJ implants typically rely on detailed in silico modelling derived from subject-specific computed tomography (CT) scans of the mandible. However, generating highly detailed finite element (FE) models is computationally expensive. Although structural simplifications of the mandible are known to influence mechanical behaviour, their quantitative impact on TMJ implant evaluation has not been systematically investigated. This study examines the influence of three modelling simplifications on stress-strain predictions in intact and implanted mandibles: (i) a detailed segmented mandible with tissue-specific material properties (Model 1), (ii) a simplified mandible comprising cortical bone only (Model 2), and (iii) a further simplified mandible excluding dental crowns (Model 3). Both narrow and standard TMJ implants were analysed under osseointegrated and non-osseointegrated conditions, resulting in fifteen FE models. Physiological clenching activities were simulated. Compared with the detailed model, simplified models showed reductions of up to 50% in maximum principal strain in bone and up to 44% in von Mises stress in TMJ implants, while preserving spatial stress-strain trends. These findings indicate that simplified models may be suitable for preliminary implant design, whereas detailed FE modelling remains essential for final pre-clinical evaluation.

bioengineering↗

bioRxiv2025

Extracellular redox sensors control the protein secretion stress response in Streptomyces

Streptomyces secondary metabolites account for over half of all clinically used antibiotics, as well as numerous antifungal agents, anticancer compounds, and immunosuppressants. Two-component systems, which are widespread in bacteria, are key regulators of antibiotic production in Streptomyces species, yet their activating signals remain poorly understood. CutRS was the first two-component system identified in the genus Streptomyces and deletion of cutRS in Streptomyces coelicolor was shown to enhance antibiotic production, although its CutR regulon does not include any biosynthetic genes. Here, we used Streptomyces venezuelae to further investigate CutRS function. We show that deletion of cutRS leads to an increase in growth rate and a reversal of the typical glucose-mediated carbon catabolite repression typically observed in Streptomyces species. We also demonstrate that CutR DNA binding is glucose-dependent, but CutR does not directly regulate genes involved in growth, antibiotic biosynthesis, or glucose metabolism. The only CutR targets conserved in both S. coelicolor and S. venezuelae are the foldase genes htrA3 and htrB, which are involved in the protein secretion stress response. Consistent with this, we show that CutS homologues all contain two conserved cysteine residues in their extracellular sensor domains and that changing these residues to serine constitutively activates S. venezuelae CutRS. We propose that failure of a disulfide bond to form between these cysteine residues indicates secretion stress and leads to activation of the CutRS system and the secretion stress response. IMPORTANCEStreptomyces bacteria are the primary source of clinically useful antibiotics. While many two-component systems have been linked to antibiotic biosynthesis in Streptomyces species, few have been well characterized. Here, we characterize a secretion stress sensing two-component system called CutRS and propose a model for how the sensor kinase detects extracellular protein misfolding via two highly conserved cysteine residues. Importantly, we also show that deletion of cutRS triggers antibiotic overproduction in the presence of glucose. Since glucose normally represses antibiotic biosynthesis in Streptomyces species through carbon catabolite repression, this finding reveals a simple genetic route to bypass this barrier. This has significant implications for antibiotic discovery pipelines and industrial production, where glucose-rich media are preferred for cost and scalability. Our results position CutRS as a key target for future strain improvement strategies.

microbiology↗

bioRxiv2024

Accelerating whole-genome alignment in the age of complete genome assemblies

Recent advancements in long-read sequencing and assembly methods have ushered in an era of high-quality genome assemblies. Modern assemblies commonly feature megabase-long sequences frequently spanning entire chromosomes. The increase in the assembly contiguity and the reduced number of assembly contigs also implies that whole-genome alignment is no longer an embarrassingly parallel problem. The conventional method of aligning sequences of the query genome in parallel is to utilize a single thread per sequence. This results in poor CPU utilization and long runtimes. In this work, we designed optimizations to accelerate whole-genome alignment on multi-core processors and implemented them in a commonly used aligner, minimap2. Our improvements include a fine-grained parallel chaining method and a fast mechanism for differentiating primary and secondary chains. Our approach accelerates alignment of human, plant, and primate genomes by 1.6x to 7.2x without compromising accuracy.

bioinformatics↗

bioRxiv2024

Integer programming framework for pangenome-based genome inference

Affordable genotyping methods are essential in genomics. Commonly used genotyping methods primarily support single nucleotide variants and short indels but neglect structural variants. Additionally, accuracy of read alignments to a reference genome is unreliable in highly polymorphic and repetitive regions, further impacting genotyping performance. Recent works highlight the advantage of haplotype-resolved pangenome graphs in addressing these challenges. Building on these developments, we propose a rigorous alignment-free genotyping framework. Our formulation seeks a path through the pangenome graph that maximizes the matches between the path and substrings of sequencing reads (e.g., k-mers) while minimizing recombination events (haplotype switches) along the path. We prove that this problem is NP-Hard and develop efficient integer-programming solutions. We benchmarked the algorithm using downsampled short-read datasets from homozygous human cell lines with coverage ranging from 0.1x to 10x. Our algorithm accurately estimates complete major histocompatibility complex (MHC) haplotype sequences with small edit distances from the ground-truth sequences, providing a significant advantage over existing methods on low-coverage inputs. Although our algorithm is designed for haploid samples, we discuss future extensions to diploid samples. Implementationhttps://github.com/at-cg/PHI

bioinformatics↗

bioRxiv2024

Biomechanical Evaluation of Temporomandibular Joint Implants Under Complete Mastication Cycle

To ensure the long-term success of temporomandibular joint (TMJ) implants, it is imperative to understand their biomechanical performances. This study aims to compare the biomechanical performance of two stock implants (narrow and standard) under unilateral and bilateral clenching during both osseointegrated and non-osseointegrated conditions. Finite element models of a human mandible were developed from QCT data, with the left TMJ being replaced by the implants. Six clenching tasks were simulated to evaluate stress and strain distributions in the mandible and implants. Ipsilateral clenching produced higher mandibular strains, while contralateral clenching generated larger implant stresses. Furthermore, intercuspal biting was found to have produced the highest strain (1750-1880 {micro}{varepsilon}) and stress ([~]17 MPa) in the mandible. Osseointegration reduced stresses (up to 0.14 MPa) and strains (up to 30 {micro}{varepsilon}) in mandible as well as stresses in mandibular components (up to 48 MPa) and screws (up to 71 MPa). However, during non-osseointegrated conditions, stresses in cortical bone were higher for standard TMJ implant as compared to narrow implant. This suggests possible preference of narrow implant over standard ones.

bioengineering↗

bioRxiv2024

Assembly of a segrosome by a CTP-independent ParB-like protein

The ATP- and CTP-dependent ParA-ParB-parS segrosome is a macromolecular complex that segregates chromosomes/plasmids in most bacterial species. CTP binding and hydrolysis enable ParB to slide on DNA and to bridge and condense DNA, thereby dictating the size and dynamics of the tripartite ParABS complex. Several other evolutionarily distinct systems can also segregate DNA, although the full diversity of bacterial DNA partition systems is not yet known. Here, we identify a CTP-independent ParABS system that maintains a conjugative plasmid SCP2 in the filamentous bacterium Streptomyces coelicolor. We demonstrate that an SCP2 ParB-like protein, ParT, loads onto DNA at an 18-bp parS site and diffuses away to the adjacent DNA despite lacking an apparent CTPase domain and detectable NTPase activity. We further show that parS DNA stimulates ParT transition from loading to a diffusing state to accumulate on DNA, and ParT activates the ATPase activity of its cognate partner protein ParA. We also identify numerous structural homologs of ParT, suggesting that CTP-independent diffusion on DNA might be widespread in bacteria despite being previously unappreciated. Overall, our findings uncover a CTP-independent DNA translocation as an alternative and unanticipated mechanism for the assembly of a bacterial DNA segregation complex and suggest that CTP binding and hydrolysis is not a fundamental feature of ParABS-like systems.

microbiology↗

bioRxiv2023

Haplotype-aware Sequence-to-Graph Alignment

Modern pangenome graphs are built using haplotype-resolved genome assemblies. During read mapping to a pangenome graph, prioritizing alignments that are consistent with the known haplotypes has been shown to improve genotyping accuracy. However, the existing rigorous formulations for sequence-to-graph co-linear chaining and alignment problems do not consider the haplotype paths in a pangenome graph. This often leads to spurious read alignments to those paths that are unlikely recombinations of the known haplotypes. In this paper, we develop novel formulations and algorithms for haplotype-aware sequence alignment to an acyclic pangenome graph. We consider both sequence-to-graph chaining and sequence-to-graph alignment problems. Drawing inspiration from the commonly used models for genotype imputation, we assume that a query sequence is an imperfect mosaic of the reference haplotypes. Accordingly, we extend previous chaining and alignment formulations by introducing a recombination penalty for a haplotype switch. First, we solve haplotype-aware sequence-to-graph alignment in O(|Q| | E| |[H]|) time, where Q is the query sequence, E is the set of edges, and [H] is the set of haplotypes represented in the graph. To complement our solution, we prove that an algorithm significantly faster than O(|Q| | E| |[H]|) is impossible under the Strong Exponential Time Hypothesis (SETH). Second, we propose a haplotype-aware chaining algorithm that runs in O(|[H]| N log |[H]|N) time after graph preprocessing, where N is the count of input anchors. We then establish that a chaining algorithm significantly faster than O(|[H]|N) is impossible under SETH. As a proof-of-concept of our algorithmic solutions, we implemented the chaining algorithm in the Minichain aligner (https://github.com/at-cg/minichain). We demonstrate the advantage of the algorithm by aligning sequences sampled from human major histocompatibility complex (MHC) to a pangenome graph of 60 MHC haplotypes. The proposed algorithm offers better consistency with ground-truth recombinations when compared to a haplotype-agnostic algorithm.

bioinformatics↗

bioRxiv2023

Identification of novel tail-anchored membrane proteins integrated by the bacterial twin-arginine translocase

The twin arginine protein transport (Tat) system exports folded proteins across the cytoplasmic membranes of prokaryotes and the energy transducing membranes of plant thylakoids and mitochondria. Proteins are targeted to the Tat machinery by N-terminal signal peptides with a conserved twin arginine motif, and some substrates are exported as heterodimers where the signal peptide is present on one of the partner proteins. A subset of Tat substrates is found in the membrane. Tat-dependent membrane proteins usually have large globular domains and a single transmembrane helix present at the N- or C-terminus. Five Tat substrates that have C-terminal transmembrane helices have previously been characterised in the model bacterium Escherichia coli. Each of these is an iron-sulphur cluster-containing protein involved in electron transfer from hydrogen or formate. Here we have undertaken a bioinformatic search to identify further tail-anchored Tat substrates encoded in bacterial genomes. Our analysis has revealed additional tail-anchored iron-sulphur proteins associated in modules with either a b-type cytochrome or a quinol oxidase. We also identified further candidate tail-anchored Tat substrates, particularly among members of the actinobacterial genus, that are not predicted to contain cofactors. Using reporter assays we show experimentally that six of these have both N-terminal Tat signal peptides and C-terminal transmembrane helices. The newly-identified proteins include a carboxypeptidase and a predicted protease, and four sortase substrates for which membrane integration is a pre-requisite for covalent attachment to the cell wall.

microbiology↗

bioRxiv2023

Barley cultivars shape the abundance, phenotype, genotype and gene expression of their associated microbiota by differential root exudate secretion

Plant associated microbes play vital roles in promoting plant growth and health, with plants secreting root exudates into the rhizosphere to attract beneficial microbes. Exudate composition defines the nature of microbial recruitment, with different plant species attracting distinct microbiota to enable optimal adaptation to the soil environment. To more closely examine the relationship between plant genotype and microbial recruitment, we analysed the rhizosphere microbiomes of landrace (Chevallier) and modern (NFC Tipple) barley cultivars. Distinct differences were observed between the plant-associated microbiomes of the two cultivars, with the plant-growth promoting rhizobacterial genus Pseudomonas substantially more abundant in the Tipple rhizosphere. Striking differences were also observed between the phenotypes of recruited Pseudomonas populations, alongside distinct genotypic clustering by cultivar. Cultivar-driven Pseudomonas selection was driven by root exudate composition, with the greater abundance of hexose sugars secreted from Tipple roots attracting microbes better adapted to growth on these metabolites, and vice versa. Cultivar-driven selection also operates at the molecular level, with both gene expression and the abundance of ecologically relevant loci differing between Tipple and Chevallier Pseudomonas isolates. Finally, cultivar-driven selection is important for plant health, with both cultivars showing a distinct preference for microbes selected by their genetic siblings in rhizosphere transplantation assays.

microbiology↗

bioRxiv2023

Co-linear Chaining on Pangenome Graphs

Pangenome reference graphs are useful in genomics because they compactly represent the genetic diversity within a species, a capability that linear references lack. However, efficiently aligning sequences to these graphs with complex topology and cycles can be challenging. The seed-chain-extend based alignment algorithms use co-linear chaining as a standard technique to identify a good cluster of exact seed matches that can be combined to form an alignment. Recent works show how the co-linear chaining problem can be efficiently solved for acyclic pangenome graphs by exploiting their small width [Makinen et al., TALG19] and how incorporating gap cost in the scoring function improves alignment accuracy [Chandra and Jain, RECOMB23]. However, it remains open on how to effectively generalize these techniques for general pangenome graphs which contain cycles. Here we present the first practical formulation and an exact algorithm for co-linear chaining on cyclic pangenome graphs. We rigorously prove the correctness and computational complexity of the proposed algorithm. We evaluate the empirical performance of our algorithm by aligning simulated long reads from the human genome to a cyclic pangenome graph constructed from 95 publicly available haplotype-resolved human genome assemblies. While the existing heuristic-based algorithms are faster, the proposed algorithm provides a significant advantage in terms of accuracy. Implementationhttps://github.com/at-cg/PanAligner

bioinformatics↗

bioRxiv2022

Sequence to graph alignment using gap-sensitive co-linear chaining

Co-linear chaining is a widely used technique in sequence alignment tools that follow seed-filter-extend methodology. It is a mathematically rigorous approach to combine short exact matches. For colinear chaining between two sequences, efficient subquadratic-time chaining algorithms are well-known for linear, concave and convex gap cost functions [Eppstein et al. JACM92]. However, developing extensions of chaining algorithms for directed acyclic graphs (DAGs) has been challenging. Recently, a new sparse dynamic programming framework was introduced that exploits small path cover of pangenome reference DAGs, and enables efficient chaining [Makinen et al. TALG19, RECOMB18]. However, the underlying problem formulation did not consider gap cost which makes chaining less effective in practice. To address this, we develop novel problem formulations and optimal chaining algorithms that support a variety of gap cost functions. We demonstrate empirically the ability of our provably-good chaining implementation to align long reads more precisely in comparison to existing aligners. For mapping simulated long reads from human genome to a pangenome DAG of 95 human haplotypes, we achieve 98.7% precision while leaving < 2% reads unmapped. Implementationhttps://github.com/at-cg/minichain

bioinformatics↗