Biomedical subjects

S Cenk Sahinalp

Publications and source records attributed to S Cenk Sahinalp.

10 recordsLinked to original sources

PubMed2025

Long-read sequencing of single cell-derived melanoma subclones reveals divergent and parallel genomic and epigenomic evolutionary trajectories.

Tumor evolution is driven by various mutational processes, ranging from single-nucleotide variants (SNVs) to large structural variants (SVs) to dynamic shifts in DNA methylation. Current short-read sequencing methods struggle to accurately capture the full spectrum of these genomic and epigenomic alterations due to inherent technical limitations. To overcome that, here we introduce an approach for long-read sequencing of single-cell derived subclones, and use it to profile 23 subclones of a mouse melanoma cell line, characterized with distinct growth phenotypes and treatment responses. We develop a computational framework for harmonization and joint analysis of different variant types in the evolutionary context. Uniquely, our framework enables detection of recurrent amplifications of putative driver genes, generated by independent SVs across different lineages, suggesting parallel evolution. In addition, our approach revealed gradual and lineage-specific methylation changes associated with aggressive clonal phenotypes. We also show our set of phylogeny-constrained variant calls along with openly released sequencing data can be a valuable resource for the development of new computational methods.

Journal Article↗

PubMed2024

Stochastic modeling 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 a 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. Sublines previously observed to be resistant to anti-CTLA4 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. A record of this paper's transparent peer review process is included in the supplemental information.

Animals↗

PubMed2006

Distance based algorithms for small biomolecule classification and structural similarity search.

MOTIVATION: Structural similarity search among small molecules is a standard tool used in molecular classification and in-silico drug discovery. The effectiveness of this general approach depends on how well the following problems are addressed. The notion of similarity should be chosen for providing the highest level of discrimination of compounds wrt the bioactivity of interest. The data structure for performing search should be very efficient as the molecular databases of interest include several millions of compounds. RESULTS: In this paper we focus on the k-nearest-neighbor search method, which, until recently was not considered for small molecule classification. The few recent applications of k-nn to compound classification focus on selecting the most relevant set of chemical descriptors which are then compared under standard Minkowski distance L(p). Here we show how to computationally design the optimal weighted Minkowski distance wL(p) for maximizing the discrimination between active and inactive compounds wrt bioactivities of interest. We then show how to construct pruning based k-nn search data structures for any wL(p) distance that minimizes similarity search time. The accuracy achieved by our classifier is better than the alternative LDA and MLR approaches and is comparable to the ANN methods. In terms of running time, our classifier is considerably faster than the ANN approach especially when large data sets are used. Furthermore, our classifier quantifies the level of bioactivity rather than returning a binary decision and thus is more informative than the ANN approach.

Algorithms↗

PubMed2006

RNA-RNA interaction prediction and antisense RNA target search.

Recent studies demonstrating the existence of special noncoding "antisense" RNAs used in post transcriptional gene regulation have received considerable attention. These RNAs are synthesized naturally to control gene expression in C. elegans, Drosophila, and other organisms; they are known to regulate plasmid copy numbers in E. coli as well. Small RNAs have also been artificially constructed to knock out genes of interest in humans and other organisms for the purpose of finding out more about their functions. Although there are a number of algorithms for predicting the secondary structure of a single RNA molecule, no such algorithm exists for reliably predicting the joint secondary structure of two interacting RNA molecules or measuring the stability of such a joint structure. In this paper, we describe the RNA-RNA interaction prediction (RIP) problem between an antisense RNA and its target mRNA and develop efficient algorithms to solve it. Our algorithms minimize the joint free energy between the two RNA molecules under a number of energy models with growing complexity. Because the computational resources needed by our most accurate approach is prohibitive for long RNA molecules, we also describe how to speed up our techniques through a number of heuristic approaches while experimentally maintaining the original accuracy. Equipped with this fast approach, we apply our method to discover targets for any given antisense RNA in the associated genome sequence.

Adenosine Triphosphatases↗

PubMed2005

Manipulating multiple sequence alignments via MaM and WebMaM.

MaM is a software tool that processes and manipulates multiple alignments of genomic sequence. MaM computes the exact location of common repeat elements, exons and unique regions within aligned genomics sequences using a variety of user identified programs, databases and/or tables. The program can extract subalignments, corresponding to these various regions of DNA to be analyzed independently or in conjunction with other elements of genomic DNA. Graphical displays further allow an assessment of sequence variation throughout these different regions of the aligned sequence, providing separate displays for their repeat, non-repeat and coding portions of genomic DNA. The program should facilitate the phylogenetic analysis and processing of different portions of genomic sequence as part of large-scale sequencing efforts. MaM source code is freely available for non-commercial use at http://compbio.cs.sfu.ca/MAM.htm; and the web interface WebMaM is hosted at http://atgc.lirmm.fr/mam.

Exons↗

PubMed2004

The role of unequal crossover in alpha-satellite DNA evolution: a computational analysis.

Human DNA consists of a large number of tandem repeat sequences. Such sequences are usually called satellites, with the primary example being the centromeric alpha-satellite DNA. The basic repeat unit of the alpha-satellite DNA is a 171 bp monomer. Arbitrary monomer pairs usually have considerable sequence divergence (20-40%). However, with the exception of peripheral alpha-satellite DNA, monomers can be grouped into blocks of k-monomers (4 < or = k < or = 20) between which the divergence rate is much smaller (e.g., 5%). Perhaps the simplest and best understood mechanism for tandem repeat array evolution is unequal crossover. Although it is possible that alpha-satellite sequences developed as a result of subsequent unequal crossovers only, no formal computational framework seems to have been developed to verify this possibility. In this paper, we develop such a framework and report on experiments which imply that pericentromeric alpha-satellite segments (which are devoid of higher order structure) are evolutionarily distinct from the higher order repeat segments. It is likely that the higher order repeats developed independently in distinct regions of the genome and were carried into their current locations through an unknown mechanism of transposition.

Algorithms↗

PubMed2004

Identifying uniformly mutated segments within repeats.

Given a long string of characters from a constant size alphabet we present an algorithm to determine whether its characters have been generated by a single i.i.d. random source. More specifically, consider all possible n-coin models for generating a binary string S, where each bit of S is generated via an independent toss of one of the n coins in the model. The choice of which coin to toss is decided by a random walk on the set of coins where the probability of a coin change is much lower than the probability of using the same coin repeatedly. We present a procedure to evaluate the likelihood of a n-coin model for given S, subject a uniform prior distribution over the parameters of the model (that represent mutation rates and probabilities of copying events). In the absence of detailed prior knowledge of these parameters, the algorithm can be used to determine whether the a posteriori probability for n=1 is higher than for any other n>1. Our algorithm runs in time O(l4logl), where l is the length of S, through a dynamic programming approach which exploits the assumed convexity of the a posteriori probability for n. Our test can be used in the analysis of long alignments between pairs of genomic sequences in a number of ways. For example, functional regions in genome sequences exhibit much lower mutation rates than non-functional regions. Because our test provides means for determining variations in the mutation rate, it may be used to distinguish functional regions from non-functional ones. Another application is in determining whether two highly similar, thus evolutionarily related, genome segments are the result of a single copy event or of a complex series of copy events. This is particularly an issue in evolutionary studies of genome regions rich with repeat segments (especially tandemly repeated segments).

Algorithms↗

PubMed2003

Analysis of primate genomic variation reveals a repeat-driven expansion of the human genome.

We performed a detailed analysis of both single-nucleotide and large insertion/deletion events based on large-scale comparison of 10.6 Mb of genomic sequence from lemur, baboon, and chimpanzee to human. Using a human genomic reference, optimal global alignments were constructed from large (>50-kb) genomic sequence clones. These alignments were examined for the pattern, frequency, and nature of mutational events. Whereas rates of single-nucleotide substitution remain relatively constant (1-2 x 10(-9) substitutions/site/year), rates of retrotransposition vary radically among different primate lineages. These differences have lead to a 15%-20% expansion of human genome size over the last 50 million years of primate evolution, 90% of it due to new retroposon insertions. Orthologous comparisons with the chimpanzee suggest that the human genome continues to significantly expand due to shifts in retrotransposition activity. Assuming that the primate genome sequence we have sampled is representative, we estimate that human euchromatin has expanded 30 Mb and 550 Mb compared to the primate genomes of chimpanzee and lemur, respectively.

Animals↗

PubMed2002

An algorithmic analysis of the role of unequal crossover in alpha-satellite DNA evolution.

Human DNA consists of a large number of tandem repeat sequences. Such sequences are usually called satellites, with the primary example being the centromeric alpha-satellite DNA. The basic repeat unit of the alpha-satellite DNA is a 171 bp monomer. However, with the exception of peripheral alpha-satellite DNA, monomers can be grouped into blocks of k-monomers (4 < k < 20) between which the divergence rate is much smaller (e.g. 5%). Perhaps the simplest and best understood mechanism for tandem repeat array evolution is the unequal crossover. Although it is possible that the alpha-satellite sequence developed as a result of subsequent unequal crossovers only, no formal computational framework seems to have been developed to verify this possibility. In this paper we develop such a framework and perform experiments which seem to indicate that pericentromeric alpha-satellite segments (which are devoid of higher-order structure) are evolutionarily distinct from the higher-order repeat segments. It is likely that the higher order repeats developed independently in distinct regions of the genome and were carried into their current locations through an unknown mechanism of transposition.

Algorithms↗

PubMedDate not supplied

Comparative QSAR- and fragments distribution analysis of drugs, druglikes, metabolic substances, and antimicrobial compounds.

A number of binary QSAR models have been developed using methods of artificial neural networks, k-nearest neighbors, linear discriminative analysis, and multiple linear regression and have been compared for their ability to recognize five types of chemical compounds that include conventional drugs, inactive druglikes, antimicrobial substituents, and bacterial and human metabolites. Thus, 20 binary classifiers have been created using a variety of 'inductive' and traditional 2D QSAR descriptors which allowed up to 99% accurate separation of the studied groups of activities. The comparison of the performance by four computational approaches demonstrated that the neural nets result in generally more accurate predictions, followed closely by k-nearest neighbors methods. It has also been demonstrated that complementation of 'inductive' descriptors with conventional QSAR parameters does not generally improve the quality of resulting solutions, conforming high predictive ability of 'inductive' variables. The conducted comparative QSAR analysis based on a novel linear optimization approach has helped to identify the extent of overlapping between the studied groups of compounds, such as cross-recognition of bacterial metabolites and antimicrobial compounds reflecting their immanent resemblance and similar origin. Human metabolites have been characterized as a very distinctive class of substances, separated from all other groups in the descriptors space and exhibiting different QSAR behavior. The analysis of unique structural fragments and substituents revealed inhomogeneous scale-free organization of human metabolites illustrating the fact that certain molecular scaffolds (such as sugars and nucleotides) may be strongly favored by natural evolution. The established scale-free organization of human metabolites has been contemplated as a factor of their unique positioning in the descriptors space and their distinctive QSAR properties. It is anticipated that the study may bring additional insight into QSAR determinants for conventional drugs, inactive chemicals, and metabolic substances and may help in rationalizing design and discovery of novel antimicrobials and human therapeutics with improved, metabolite-like properties.

Anti-Infective Agents↗