Biomedical subjects

Steven Skiena

Publications and source records attributed to Steven Skiena.

7 recordsLinked to original sources

PubMed2006

Reduction of the rate of poliovirus protein synthesis through large-scale codon deoptimization causes attenuation of viral virulence by lowering specific infectivity.

Exploring the utility of de novo gene synthesis with the aim of designing stably attenuated polioviruses (PV), we followed two strategies to construct PV variants containing synthetic replacements of the capsid coding sequences either by deoptimizing synonymous codon usage (PV-AB) or by maximizing synonymous codon position changes of the existing wild-type (wt) poliovirus codons (PV-SD). Despite 934 nucleotide changes in the capsid coding region, PV-SD RNA produced virus with wild-type characteristics. In contrast, no viable virus was recovered from PV-AB RNA carrying 680 silent mutations, due to a reduction of genome translation and replication below a critical level. After subcloning of smaller portions of the AB capsid coding sequence into the wt background, several viable viruses were obtained with a wide range of phenotypes corresponding to their efficiency of directing genome translation. Surprisingly, when inoculated with equal infectious doses (PFU), even the most replication-deficient viruses appeared to be as pathogenic in PV-sensitive CD155tg (transgenic) mice as the PV(M) wild type. However, infection with equal amounts of virus particles revealed a neuroattenuated phenotype over 100-fold. Direct analysis indicated a striking reduction of the specific infectivity of PV-AB-type virus particles. Due to the distribution effect of many silent mutations over large genome segments, codon-deoptimized viruses should have genetically stable phenotypes, and they may prove suitable as attenuated substrates for the production of poliovirus vaccines.

Animals↗

PubMed2005

Copy correction and concerted evolution in the conservation of yeast genes.

The yeast Saccharomyces cerevisiae and other members of the genus Saccharomyces are descendants of an ancient whole-genome duplication event. Although most of the duplicate genes have since been deleted, many remain, and so there are many pairs of related genes. We have found that poorly expressed genes diverge rapidly from their paralog, while highly expressed genes diverge little, if at all. This lack of divergence of highly expressed paralogous gene pairs seems to involve gene correction: one member of the pair "corrects" the sequence of its twin, and so the gene pair evolves as a unit. This correction presumably involves gene conversion and could occur via a reverse-transcribed cDNA intermediate. Such correction events may also occur in other organisms. These results support the idea that copies of poorly expressed genes are preserved when they diverge to take on new functions, while copies of highly expressed genes are preserved when they are needed to provide additional gene product for the original function.

Base Sequence↗

PubMed2003

Natural selection and algorithmic design of mRNA.

Messenger RNA (mRNA) sequences serve as templates for proteins according to the triplet code, in which each of the 4(3) = 64 different codons (sequences of three consecutive nucleotide bases) in RNA either terminate transcription or map to one of the 20 different amino acids (or residues) which build up proteins. Because there are more codons than residues, there is inherent redundancy in the coding. Certain residues (e.g., tryptophan) have only a single corresponding codon, while other residues (e.g., arginine) have as many as six corresponding codons. This freedom implies that the number of possible RNA sequences coding for a given protein grows exponentially in the length of the protein. Thus nature has wide latitude to select among mRNA sequences which are informationally equivalent, but structurally and energetically divergent. In this paper, we explore how nature takes advantage of this freedom and how to algorithmically design structures more energetically favorable than have been built through natural selection. In particular: (1) Natural Selection--we perform the first large-scale computational experiment comparing the stability of mRNA sequences from a variety of organisms to random synonymous sequences which respect the codon preferences of the organism. This experiment was conducted on over 27,000 sequences from 34 microbial species with 36 genomic structures. We provide evidence that in all genomic structures highly stable sequences are disproportionately abundant, and in 19 of 36 cases highly unstable sequences are disproportionately abundant. This suggests that the stability of mRNA sequences is subject to natural selection. (2) Artificial Selection--motivated by these biological results, we examine the algorithmic problem of designing the most stable and unstable mRNA sequences which code for a target protein. We give a polynomial-time dynamic programming solution to the most stable sequence problem (MSSP), which is asymptotically no more complex than secondary structure prediction. We show that the corresponding least stable sequence problem (LSSP) is NP-complete, and develop two heuristics for the construction of such sequences. We have implemented these algorithms, and present experimental results placing the high/low stability sequences in context with both wildtype and random encodings. Our implementation has already been applied to the design of RNA "code-words" creating little or no secondary structure in RNA computing (Brenneman and Condon, 2001; Marathe et al., 2001), and we anticipate a variety of other applications of this work to sequence design problems (Skiena, 2001).

Algorithms↗

PubMed2003

Deconvolving sequence variation in mixed DNA populations.

We present an original approach to identifying sequence variants in a mixed DNA population from sequence trace data. The heart of the method is based on parsimony: given a wildtype DNA sequence, a set of observed variations at each position collected from sequencing data, and a complete catalog of all possible mutations, determine the smallest set of mutations from the catalog that could fully explain the observed variations. The algorithmic complexity of the problem is analyzed for several classes of mutations, including block substitutions, single-range deletions, and single-range insertions. The reconstruction problem is shown to be NP-complete for single-range insertions and deletions, while for block substitutions, single character insertion, and single character deletion mutations, polynomial time algorithms are provided. Once a minimum set of mutations compatible with the observed sequence is found, the relative frequency of those mutations is recovered by solving a system of linear equations. Simulation results show the algorithm successfully deconvolving mutations in p53 known to cause cancer. An extension of the algorithm is proposed as a new method of high throughput screening for single nucleotide polymorphisms by multiplexing DNA.

Algorithms↗

PubMed2002

Analysis techniques for microarray time-series data.

We address possible limitations of publicly available data sets of yeast gene expression. We study the predictability of known regulators via time-series analysis, and show that less than 20% of known regulatory pairs exhibit strong correlations in the Cho/Spellman data sets. By analyzing known regulatory relationships, we designed an edge detection function which identified candidate regulations with greater fidelity than standard correlation methods. We develop general methods for integrated analysis of coarse time-series data sets. These include 1) methods for automated period detection in a predominately cycling data set and 2) phase detection between phase-shifted cyclic data sets. We show how to properly correct for the problem of comparing correlation coefficients between pairs of sequences of different lengths and small alphabets. Finally, we note that the correlation coefficient of sequences over alphabets of size two can exhibit very counterintuitive behavior when compared with the Hamming distance.

Algorithms↗

PubMed2002

Genomic sorting with length-weighted reversals.

Current algorithmic studies of genome rearrangement ignore the length of reversals (or inversions); rather, they only count their number. We introduce a new cost model in which the lengths of the reversed sequences play a role, allowing more flexibility in accounting for mutation phenomena. Our focus is on sorting unsigned (unoriented) permutations by reversals; since this problem remains difficult (NP-hard) in our new model, the best we can hope for are approximation results. We propose an efficient, novel algorithm that takes (a monotonic function f of) length into account as an optimization criterion and study its properties. Our results include an upper bound of O(fn lg2n) for any additive cost measure f on the cost of sorting any n-element permutation, and a guaranteed approximation ratio of O(lg2n) times optimal for sorting a given permutation. Our work poses some interesting questions to both biologists and computer scientists and suggests some new bioinformatic insights that are currently being studied.

Algorithms↗

PubMedDate not supplied

Spatial analysis of news sources.

People in different places talk about different things. This interest distribution is reflected by the newspaper articles circulated in a particular area. We use data from our large-scale newspaper analysis system (Lydia) to make entity datamaps, a spatial visualization of the interest in a given named entity. Our goal is to identify entities which display regional biases. We develop a model of estimating the frequency of reference of an entity in any given city from the reference frequency centered in surrounding cities, and techniques for evaluating the spatial significance of this distribution.

Journal Article↗