Biology subjects

Sahinalp, C.

Publications and source records attributed to Sahinalp, C..

16 recordsLinked to original sources

bioRxiv2026

LOCALE: Local-Alignment Embeddings for Noise-Robust DNA Search at SRA Scale

Searching petabase-scale repositories of raw sequencing data such as the NIH Sequence Read Archive (SRA) could transform biological discovery, but existing methods either do not scale well or rely on exact k-mer matching that is brittle to sequencing errors and biological divergence. We recast sequence search as dense retrieval: we learn vector embeddings whose inner-product similarity ranks locally aligned sequences above unaligned ones. Our key observation is that effective retrieval does not require accurate regression of global edit distance--it only requires that sequences with better local alignments score higher than sequences with worse ones. We train a DNABERT-2 encoder with an InfoNCE objective on biologically informed augmentations: overlapping crops of parent sequences corrupted with substitutions, insertions, and deletions. On a 50-accession SRA benchmark, LOCALE maintains 62.4% average Recall@Rq at a 10% mutation rate, while every baseline we evaluated falls below 60% Recall@Rq in the noisy-query setting. The advantage holds at scale: on a 500-accession, 15-Gbp benchmark, LOCALE achieves AUPRC 0.508 at 10% mutation versus 0.129 for MetaGraph.

bioinformatics↗

bioRxiv2026

Identifying Robust Subclonal Structures through Tumor Progression Tree Alignment

Understanding and comparing tumor evolutionary histories is fundamental to cancer genomics. Clonal trees, used to model tumor progression, are rooted, unordered trees in which each node represents a subclone labeled by a set of distinct mutations. To compare two clonal trees, we introduce omlta, the optimal multi-label tree alignment, which removes the minimum number of mutation labels from the trees, so that the remaining trees are isomorphic. Computing omlta is NP-hard. Here, we present an algorithm to compute the omlta, with a running time of [Formula] where L [≥] 1 is the total number of mutation labels occurring in the input trees and k is the minimum possible number of mutation labels that need to be removed for the alignment. Our implementation (https://github.com/algo-cancer/omlta) is the first computational tool for determining the optimal alignment between clonal trees. We applied omlta to 126 cases from the TRACERx study on non-small cell lung cancers and some melanoma single-cell data.

cancer biology↗

bioRxiv2026

GenCore: Genomic distance estimation using Locally Consistent Parsing

In the era of exponential data generation, a fast, consistent, and efficient string processing technique is necessary to represent extensive genomic data. One of the earliest string processing techniques, predating MinHash and minimizer-based sketching, is Locally Consistent Parsing (LCP). This technique partitions an input string and identifies short, exactly occurring substrings called cores, which collectively cover the input string while maintaining Partition and Labeling Consistency. The iterative application of LCP yields progressively longer cores in a compressed format, thereby substantially enhancing the efficiency of genomic sequence representation and subsequent downstream analysis. We have previously developed Lcptools as the first iterative implementation of LCP for the DNA alphabet and demonstrated its effectiveness in identifying cores with minimal collisions. Here, we introduce GO_SCPLOWENC_SCPLOWCO_SCPLOWOREC_SCPLOW, a computational method that leverages LCP cores for the first time to sketch and estimate genomic distances for closely related large genomes, and successfully reconstruct simulated progression trees. GO_SCPLOWENC_SCPLOWCO_SCPLOWOREC_SCPLOW also successfully recapitulates primate phylogeny using both telomere-totelomere (T2T) assemblies and the PacBio HiFi reads for assembly-free comparisons. AvailabilityGO_SCPLOWENC_SCPLOWCO_SCPLOWOREC_SCPLOW is available at https://github.com/BilkentCompGen/gencore

bioinformatics↗

bioRxiv2024

Learning-Augmented Sketching Offers Improved Performance for Privacy Preserving and Secure GWAS

The introduction of trusted execution environments (TEEs), such as secure enclaves provided by the Intel SGX technology has enabled secure and privacy-preserving computation on the cloud. The stringent resource limitations, such as memory constraints, required by some TEEs necessitates the development of computational approaches with reduced memory usage, such as sketching. One example is the SkSES method for GWAS on a cohort of case and control samples from multiple institutions, which identifies the most significant SNPs in a privacy-preserving manner without disclosing sensitive genotype information to other institutions or the cloud service provider. Here we show how to improve the performance of SkSES on large datasets by augmenting it with a learning-augmented approach. Specifically, we show how individual institutions can perform smaller scale GWAS on their own datasets and identify two sets of variants according to certain criteria, which are then used to guide the sketching process to more accurately identify significant variants over the collective dataset. The new method achieves up to 40% accuracy gain compared to the original SkSES method under the same memory constraints on datasets we tested on. The code is available at https://github.com/alreadydone/sgx-genome-variants-search. Contactcenk.sahinalp@nih.gov

bioinformatics↗

bioRxiv2024

Stochastic modelling of single-cell gene expression adaptation reveals non-genomic contribution to evolution of tumor subclones

Cancer progression is an evolutionary process driven by the selection of cells adapted to gain growth advantage. We present the first formal study on the adaptation of gene expression in subclonal evolution. We model evolutionary changes in gene expression as stochastic Ornstein-Uhlenbeck processes, jointly leveraging the evolutionary history of subclones and single-cell expression data. Applying our model to sublines derived from single cells of a mouse melanoma revealed that sublines with distinct phenotypes are underlined by different patterns of gene expression adaptation, indicating non-genetic mechanisms of cancer evolution. Interestingly, sublines previously observed to be resistant to anti-CTLA-4 treatment showed adaptive expression of genes related to invasion and non-canonical Wnt signaling, whereas sublines that responded to treatment showed adaptive expression of genes related to proliferation and canonical Wnt signaling. Our results suggest that clonal phenotypes emerge as the result of specific adaptivity patterns of gene expression.

cancer biology↗

bioRxiv2024

Determining Optimal Placement of Copy Number Aberration Impacted Single Nucleotide Variants in a Tumor Progression History

Intratumoral heterogeneity arises as a result of genetically distinct subclones emerging during tumor progression. These subclones are characterized by various types of somatic genomic aberrations, with single nucleotide variants (SNVs) and copy number aberrations (CNAs) being the most prominent. While single-cell sequencing provides powerful data for studying tumor progression, most existing and newly generated sequencing datasets are obtained through conventional bulk sequencing. Most of the available methods for studying tumor progression from multi-sample bulk sequencing data are either based on the use of SNVs from genomic loci not impacted by CNAs or designed to handle a small number of SNVs via enumerating their possible copy number trees. In this paper, we introduce DETOPT, a combinatorial optimization method for accurate tumor progression tree inference that places SNVs impacted by CNAs on trees of tumor progression with minimal distortion on their variant allele frequencies observed across available samples of a tumor. We show that on simulated data DETOPT provides more accurate tree placement of SNVs impacted by CNAs than the available alternatives. When applied to a set of multi-sample bulk exome-sequenced tumor metastases from a treatment-refractory, triple-positive metastatic breast cancer, DETOPT reports biologically plausible trees of tumor progression, identifying the tree placement of copy number state gains and losses impacting SNVs, including those in clinically significant genes.

cancer biology↗

bioRxiv2024

Geny: A Genotyping Tool for Allelic Decomposition of Killer Cell Immunoglobulin-Like Receptor Genes

Accurate genotyping of Killer cell Immunoglobulin-like Receptor (KIR) genes plays a pivotal role in enhancing our understanding of innate immune responses, disease correlations, and the advancement of personalized medicine. However, due to the high variability of the KIR region and high level of sequence similarity among different KIR genes, the currently available genotyping methods are unable to accurately infer copy numbers, genotypes and haplotypes of individual KIR genes from next-generation sequencing data. Here we introduce Geny, a new computational tool for precise genotyping of KIR genes. Geny utilizes available KIR haplotype databases and proposes a novel combination of expectation-maximization filtering schemes and integer linear programming-based combinatorial optimization models to resolve ambiguous reads, provide accurate copy number estimation and estimate the haplotype of each copy for the genes within the KIR region. We evaluated Geny on a large set of simulated short-read datasets covering the known validated KIR region assemblies and a set of Illumina short-read samples sequenced from 25 validated samples from the Human Pangenome Reference Consortium collection and showed that it outperforms the existing genotyping tools in terms of accuracy, precision and recall. We envision Geny becoming a valuable resource for understanding immune system response and consequently advancing the field of patient-centric medicine.

bioinformatics↗

bioRxiv2023

Melanoma clonal subline analysis uncovers heterogeneity-driven immunotherapy resistance mechanisms

Intratumoral heterogeneity (ITH) can promote cancer progression and treatment failure, but the complexity of the regulatory programs and contextual factors involved complicates its study. To understand the specific contribution of ITH to immune checkpoint blockade (ICB) response, we generated single cell-derived clonal sublines from an ICB-sensitive and genetically and phenotypically heterogeneous mouse melanoma model, M4. Genomic and single cell transcriptomic analyses uncovered the diversity of the sublines and evidenced their plasticity. Moreover, a wide range of tumor growth kinetics were observed in vivo, in part associated with mutational profiles and dependent on T cell-response. Further inquiry into melanoma differentiation states and tumor microenvironment (TME) subtypes of untreated tumors from the clonal sublines demonstrated correlations between highly inflamed and differentiated phenotypes with the response to anti-CTLA-4 treatment. Our results demonstrate that M4 sublines generate intratumoral heterogeneity at both levels of intrinsic differentiation status and extrinsic TME profiles, thereby impacting tumor evolution during therapeutic treatment. These clonal sublines proved to be a valuable resource to study the complex determinants of response to ICB, and specifically the role of melanoma plasticity in immune evasion mechanisms.

cancer biology↗

bioRxiv2022

Aldy 4: An efficient genotyper and star-allele caller for pharmacogenomics

High-throughput sequencing provides sufficient means for determining genotypes of clinically important pharmacogenes that can be used to tailor medical decisions to individual patients. However, pharmacogene genotyping, also known as star-allele calling, is a challenging problem that requires accurate copy number calling, structural variation discovery, variant calling and phasing within each pharmacogene copy present in the sample. Here we introduce Aldy 4, a fast and efficient tool for genotyping pharmacogenes that utilizes combinatorial optimization for accurate star-allele calling across different sequencing technologies. Aldy 4 adds support for long reads and ships with a novel phasing model and improved copy number and variant calling models. We compare Aldy 4 against the current state-of-the-art star-allele callers on a large and diverse set of samples and genes sequenced by various sequencing technologies, such as whole-genome and targeted Illumina sequencing, barcoded 10X Genomics and PacBio HiFi. We show that Aldy 4 is the most accurate star-allele caller with near-perfect accuracy in all evaluated contexts. We hope that Aldy remains an invaluable tool in the clinical toolbox even with the advent of long-read sequencing technologies. AvailabilityAldy 4 is available at https://github.com/0xTCG/aldy.

bioinformatics↗

bioRxiv2022

ImmunoTyper-SR: A Novel Computational Approach for Genotyping Immunoglobulin Heavy Chain Variable Genes using Short Read Data

Human immunoglobulin heavy chain (IGH) locus on chromosome 14 includes more than 40 functional copies of the variable gene (IGHV), which, together with the joining genes (IGHJ), diversity genes (IGHD), constant genes (IGHC) and immunoglobulin light chains, code for antibodies that identify and neutralize pathogenic invaders as a part of the adaptive immune system. Because of its highly repetitive sequence composition, the IGH locus has been particularly difficult to assemble or genotype through the use of standard short read sequencing technologies. Here we introduce ImmunoTyper-SR, an algorithmic method for genotype and CNV analysis of the germline IGHV genes using Illumina whole genome sequencing (WGS) data. ImmunoTyper-SR is based on a novel combinatorial optimization formulation that aims to minimize the total edit distance between reads and their assigned IGHV alleles from a given database, with constraints on the number and distribution of reads across each called allele. We have validated ImmunoTyper-SR on 12 individuals with Illumina WGS data from the 1000 Genomes Project, whose IGHV allele composition have been studied extensively through the use of long read and targeted sequencing platforms, as well as nine individuals from the NIAID COVID Consortium who have been subjected to WGS twice. We have then applied ImmunoTyper-SR on 585 samples from the NIAID COVID Consortium to investigate associations between distinct IGHV alleles and anti-type I IFN autoantibodies which have been linked to COVID-19 severity.

bioinformatics↗

bioRxiv2020

Proteogenomic analysis unveils the HLA Class I presented immunopeptidome in melanoma and EGFR mutant lung adenocarcinoma

Immune checkpoint inhibitor and adoptive lymphocyte transfer-based therapies have shown great therapeutic potential for cancers with high tumor mutation burden (TMB). Here, we employed mass spectrometry (MS)-based proteogenomic large-scale profiling to identify potential immunogenic human leukocyte antigen (HLA) Class I-presented peptides in both melanoma, a "hot tumor" with high TMB, and EGFR mutant lung adenocarcinoma, a "cold tumor" with low TMB. We identified several classes of neopeptides, including mutated neoantigens and more than 1000 post-translationally modified peptides representing 58 different PTMs. We constructed a cancer germline (CG) antigen database with 285 antigens and identified 42 Class I-presented CG antigens. Finally, we developed a non-canonical peptide discovery pipeline to identify 44 lncRNA-derived peptides and validated Class I binding for select neopeptides. We provide direct evidence of HLA Class I presentation of a large number of neopeptides for potential vaccine or adoptive cell therapy in melanoma and mutant EGFR lung cancer.

immunology↗

bioRxiv2020

Combinatorial Algorithms for Strain Level Metagenomic Microbial Detection and Quantification

The identification and quantification of microbial abundance at the species or strain level from sequencing data is crucial for our understanding of human health and disease. Existing approaches for microbial abundance estimation either use accurate but computationally expensive alignment-based approaches for species-level estimation or less accurate but computationally fast alignment-free approaches that fail to classify many reads accurately at the species or strain-level. Here we introduce CAMMiQ, a novel combinatorial solution to the microbial identification and abundance estimation problem, which performs better than the best used tools on simulated and real datasets with respect to the number of correctly classified reads (i.e., specificity) by an order of magnitude and resolves possible mixtures of similar genomes. As we demonstrate, CAMMiQ can better distinguish between single cells deliberately infected with distinct Salmonella strains and sequenced using scRNA-seq reads than alternative approaches. We also demonstrate that CAMMiQ is also more accurate than the best used approaches on a variety of synthetic genomic read data involving some of the most challenging bacterial genomes derived from NCBI RefSeq database; it can distinguish not only distinct species but also closely related strains of bacteria. The key methodological innovation of CAMMiQ is its use of arbitrary length, doubly-unique substrings, i.e. substrings that appear in (exactly) two genomes in the input database, instead of fixed-length, unique substrings. To resolve the ambiguity in the genomic origin of doubly-unique substrings, CAMMiQ employs a combinatorial optimization formulation, which can be solved surprisingly quickly. CAMMiQs index consists of a sparsified subset of the shortest unique and doubly-unique substrings of each genome in the database, within a user specified length range and as such it is fairly compact. In short, CAMMiQ offers more accurate genomic identification and abundance estimation than the best used alternatives while using similar computational resources. Availabilityhttps://github.com/algo-cancer/CAMMiQ

bioinformatics↗

bioRxiv2020

Identification of Conserved Evolutionary Trajectories in Tumors

MotivationAs multi-region, time-series, and single cell sequencing data become more widely available, it is becoming clear that certain tumors share evolutionary characteristics with others. In the last few years, several computational methods have been developed with the goal of inferring the subclonal composition and evolutionary history of tumors from tumor biopsy sequencing data. However, the phylogenetic trees that they report differ significantly between tumors (even those with similar characteristics). ResultsIn this paper, we present a novel combinatorial optimization method, CONETT, for detection of recurrent tumor evolution trajectories. Our method constructs a consensus tree of conserved evolutionary trajectories based on the information about temporal order of alteration events in a set of tumors. We apply our method to previously published datasets of 100 clear-cell renal cell carcinoma and 99 non-small-cell lung cancer patients and identify both conserved trajectories that were reported in the original studies, as well as new trajectories. AvailabilityCONETT is implemented in C++ and available at https://github.com/ehodzic/CONETT.

bioinformatics↗

bioRxiv2018

Sketching Algorithms for Genomic Data Analysis and Querying in a Secure Enclave

Current practices in collaborative genomic data analysis (e.g. PCAWG [1]) necessitate all involved parties to exchange individual patient data and perform all analysis locally, or use a trusted server for maintaining all data to perform analysis in a single site (e.g. the Cancer Genome Collaboratory). Since both approaches involve sharing genomic sequence data - which is typically not feasible due to privacy issues, collaborative data analysis remains to be a rarity in genomic medicine.\n\nIn order to facilitate efficient and effective collaborative or remote genomic computation we introduce SkSES (Sketching algorithms for Secure Enclave based genomic data analysiS), a computational framework for performing data analysis and querying on multiple, individually encrypted genomes from several institutions in an untrusted cloud environment. Unlike other techniques for secure/privacy preserving genomic data analysis, which typically rely on sophisticated cryptographic techniques with prohibitively large computational overheads, SkSES utilizes the secure enclaves supported by current generation microprocessor architectures such as Intels SGX. The key conceptual contribution of SkSES is its use of sketching data structures that can fit in the limited memory available in a secure enclave.\n\nWhile streaming/sketching algorithms have been developed for many applications in computer science, their feasibility in genomics has remained largely unexplored. On the other hand, even though privacy and security issues are becoming critical in genomic medicine, available cryptographic techniques based on, e.g. homomorphic encryption or garbled circuits, fail to address the performance demands of this rapidly growing field. The alternative offered by Intels SGX, a combination of hardware and software solutions for secure data analysis, is severely limited by the relatively small size of a secure enclave, a private region of the memory protected from other processes. SkSES addresses this limitation through the use of sketching data structures to support efficient secure and privacy preserving SNP analysis across individually encrypted VCF files from multiple institutions. In particular SkSES provides the users the ability to query for the \"k most significant SNPs\" among any set of user specified SNPs and any value of k - even when the total number of SNPs to be maintained is far beyond the memory capacity of the secure enclave.\n\nResultsWe tested SkSES on the complete iDASH-2017 competition data set comprised of 1000 case and 1000 control samples related to an unknown phenotype. SkSES was able to identify the top SNPs with respect to the{chi} 2 statistic, among any user specified subset of SNPs across this data set of 2000 individually encrypted complete human genomes quickly and accurately - demonstrating the feasibility of secure and privacy preserving computation for genomic medicine via Intels SGX.\n\nAvailabilityhttps://github.com/ndokmai/sgx-genome-variants-search

bioinformatics↗

bioRxiv2018

MechRNA: prediction of lncRNA mechanisms from RNA-RNA and RNA-protein interactions

MotivationLong non-coding RNAs (lncRNAs) are defined as transcripts longer than 200 nucleotides that do not get translated into proteins. Often these transcripts are processed (spliced, capped, polyadenylated) and some are known to have important biological functions. However, most lncRNAs have unknown or poorly understood functions. Nevertheless, because of their potential role in cancer, lncRNAs are receiving a lot of attention, and the need for computational tools to predict their possible mechanisms of action is more than ever. Fundamentally, most of the known lncRNA mechanisms involve RNA-RNA and/or RNA-protein interactions. Through accurate predictions of each kind of interaction and integration of these predictions, it is possible to elucidate potential mechanisms for a given lncRNA.\n\nApproachHere we introduce MechRNA, a pipeline for corroborating RNA-RNA interaction prediction and protein binding prediction for identifying possible lncRNA mechanisms involving specific targets or on a transcriptome-wide scale. The first stage uses a version of IntaRNA2 with added functionality for efficient prediction of RNA-RNA interactions with very long input sequences, allowing for large-scale analysis of lncRNA interactions with little or no loss of optimality. The second stage integrates protein binding information pre-computed by GraphProt, for both the lncRNA and the target. The final stage involves inferring the most likely mechanism for each lncRNA/target pair. This is achieved by generating candidate mechanisms from the predicted interactions, the relative locations of these interactions and correlation data, followed by selection of the most likely mechanistic explanation using a combined p-value.\n\nResultsWe applied MechRNA on a number of recently identified cancer-related lncRNAs (PCAT1, PCAT29, ARLnc1) and also on two well-studied lncRNAs (PCA3 and 7SL). This led to the identification of hundreds of high confidence potential targets for each lncRNA and corresponding mechanisms. These predictions include the known competitive mechanism of 7SL with HuR for binding on the tumor suppressor TP53, as well as mechanisms expanding what is known about PCAT1 and ARLn1 and their targets BRCA2 and AR, respectively. For PCAT1-BRCA2, the mechanism involves competitive binding with HuR, which we confirmed using HuR immunoprecipitation assays.\n\nAvailabilityMechRNA is available for download at https://bitbucket.org/compbio/mechrna\n\nContactbackofen@informatik.uni-freiburg.de, cenksahi@indiana.edu\n\nSupplementary informationSupplementary data are available at Bioinformatics online.

bioinformatics↗

bioRxiv2017

Integrative inference of subclonal tumour evolution from single-cell and bulk sequencing data

Understanding the evolutionary history and subclonal composition of a tumour represents one of the key challenges in overcoming treatment failure due to resistant cell populations. Most of the current data on tumour genetics stems from short read bulk sequencing data. While this type of data is characterised by low sequencing noise and cost, it consists of aggregate measurements across a large number of cells. It is therefore of limited use for the accurate detection of the distinct cellular populations present in a tumour and the unambiguous inference of their evolutionary relationships. Single-cell DNA sequencing instead provides data of the highest resolution for studying intra-tumour heterogeneity and evolution, but is characterised by higher sequencing costs and elevated noise rates. In this work, we develop the first computational approach that infers trees of tumour evolution from combined single-cell and bulk sequencing data. Using a comprehensive set of simulated data, we show that our approach systematically outperforms existing methods with respect to tree reconstruction accuracy and subclone identification. High fidelity reconstructions are obtained even with a modest number of single cells. We also show that combining single-cell and bulk sequencing data provides more realistic mutation histories for real tumours.

bioinformatics↗