ABSTRACT
BACKGROUND: Researchers are increasingly interested in better methods for assessing the pace of aging in older adults, including vocal analysis. The present study sought to determine whether paralinguistic vocal attributes improve estimates of the age and risk of mortality in older adults. METHODS: To measure vocal age, we curated interviews provided by male U.S. World War II Veterans in the Library of Congress collection. We used diarization to identify speakers and measure vocal features and matched recording data to mortality information. Veterans (N = 2 447) were randomly split into testing (n = 1 467) and validation (n = 980) subsets to generate estimations of vocal age and years of life remaining. Results were replicated to examine out-of-sample utility using Korean War Veterans (N = 352). RESULTS: World War II Veterans' average age was 86.08 at the time of recording and 91.28 at the time of death. Overall, 7.4% were prisoners of war, 43.3% were Army Veterans, and 29.3% were drafted. Vocal age estimates (mean absolute error = 3.255) were within 5 years of chronological age, 78.5% of the time. With chronological age held constant, older vocal age estimation was correlated with shorter life expectancy (aHR = 1.10; 95% confidence interval: 1.06-1.15; p < .001), even when adjusting for age at vocal assessment. CONCLUSIONS: Computational analyses reduced estimation error by 71.94% (approximately 8 years) and produced vocal age estimates that were correlated with both age and predicted time until death when age was held constant. Paralinguistic analyses augment other assessments for individuals when oral patient histories are recorded.
Subject(s)
Healthy Aging , Veterans , Humans , Male , Aged , Aged, 80 and over , World War II , AgingABSTRACT
Billions of dollars are being invested into developing medical artificial intelligence (AI) systems and yet public opinion of AI in the medical field seems to be mixed. Although high expectations for the future of medical AI do exist in the American public, anxiety and uncertainty about what it can do and how it works is widespread. Continuing evaluation of public opinion on AI in healthcare is necessary to ensure alignment between patient attitudes and the technologies adopted. We conducted a representative-sample survey (total N = 203) to measure the trust of the American public towards medical AI. Primarily, we contrasted preferences for AI and human professionals to be medical decision-makers. Additionally, we measured expectations for the impact and use of medical AI in the future. We present four noteworthy results: (1) The general public strongly prefers human medical professionals make medical decisions, while at the same time believing they are more likely to make culturally biased decisions than AI. (2) The general public is more comfortable with a human reading their medical records than an AI, both now and "100 years from now." (3) The general public is nearly evenly split between those who would trust their own doctor to use AI and those who would not. (4) Respondents expect AI will improve medical treatment but more so in the distant future than immediately.
Subject(s)
Artificial Intelligence , Public Opinion , Humans , Health Facilities , Anxiety , Delivery of Health CareABSTRACT
Introduction: The clock drawing task (CDT) is frequently used to aid in detecting cognitive impairment, but current scoring techniques are time-consuming and miss relevant features, justifying the creation of an automated quantitative scoring approach. Methods: We used computer vision methods to analyze the stored scanned images (N = 7,109), and an intelligent system was created to examine these files in a study of aging World Trade Center responders. Outcomes were CDT, Montreal Cognitive Assessment (MoCA) score, and incidence of mild cognitive impairment (MCI). Results: The system accurately distinguished between previously scored CDTs in three CDT scoring categories: contour (accuracy = 92.2%), digits (accuracy = 89.1%), and clock hands (accuracy = 69.1%). The system reliably predicted MoCA score with CDT scores removed. Predictive analyses of the incidence of MCI at follow-up outperformed human-assigned CDT scores. Discussion: We created an automated scoring method using scanned and stored CDTs that provided additional information that might not be considered in human scoring.
ABSTRACT
Epidemiological studies suggest that insulin resistance accelerates progression of age-based cognitive impairment, which neuroimaging has linked to brain glucose hypometabolism. As cellular inputs, ketones increase Gibbs free energy change for ATP by 27% compared to glucose. Here we test whether dietary changes are capable of modulating sustained functional communication between brain regions (network stability) by changing their predominant dietary fuel from glucose to ketones. We first established network stability as a biomarker for brain aging using two large-scale (n = 292, ages 20 to 85 y; n = 636, ages 18 to 88 y) 3 T functional MRI (fMRI) datasets. To determine whether diet can influence brain network stability, we additionally scanned 42 adults, age < 50 y, using ultrahigh-field (7 T) ultrafast (802 ms) fMRI optimized for single-participant-level detection sensitivity. One cohort was scanned under standard diet, overnight fasting, and ketogenic diet conditions. To isolate the impact of fuel type, an independent overnight fasted cohort was scanned before and after administration of a calorie-matched glucose and exogenous ketone ester (d-ß-hydroxybutyrate) bolus. Across the life span, brain network destabilization correlated with decreased brain activity and cognitive acuity. Effects emerged at 47 y, with the most rapid degeneration occurring at 60 y. Networks were destabilized by glucose and stabilized by ketones, irrespective of whether ketosis was achieved with a ketogenic diet or exogenous ketone ester. Together, our results suggest that brain network destabilization may reflect early signs of hypometabolism, associated with dementia. Dietary interventions resulting in ketone utilization increase available energy and thus may show potential in protecting the aging brain.
Subject(s)
Aging/physiology , Brain/physiology , Energy Metabolism/physiology , Feeding Behavior/physiology , Nerve Net/physiology , Adaptation, Physiological , Adolescent , Adult , Aged , Aged, 80 and over , Brain/diagnostic imaging , Cognition/physiology , Datasets as Topic , Dementia/diet therapy , Dementia/physiopathology , Dementia/prevention & control , Diet, Ketogenic , Female , Glucose/administration & dosage , Glucose/metabolism , Humans , Insulin/metabolism , Insulin Resistance/physiology , Ketones/administration & dosage , Ketones/metabolism , Magnetic Resonance Imaging , Male , Middle Aged , Neuroimaging/methods , Young AdultABSTRACT
Over the past century, personality theory and research has successfully identified core sets of characteristics that consistently describe and explain fundamental differences in the way people think, feel and behave. Such characteristics were derived through theory, dictionary analyses, and survey research using explicit self-reports. The availability of social media data spanning millions of users now makes it possible to automatically derive characteristics from behavioral data-language use-at large scale. Taking advantage of linguistic information available through Facebook, we study the process of inferring a new set of potential human traits based on unprompted language use. We subject these new traits to a comprehensive set of evaluations and compare them with a popular five factor model of personality. We find that our language-based trait construct is often more generalizable in that it often predicts non-questionnaire-based outcomes better than questionnaire-based traits (e.g. entities someone likes, income and intelligence quotient), while the factors remain nearly as stable as traditional factors. Our approach suggests a value in new constructs of personality derived from everyday human language use.
Subject(s)
Language , Social Media , Female , Humans , MaleABSTRACT
Herpesviruses establish life-long chronic infections that place infected hosts at risk for severe disease. Herpesvirus genomes readily undergo homologous recombination (HR) during productive replication, often leading to wild-type (WT) reversion during complementation of replication-defective and attenuated viruses via HR with the helper gene provided in trans. To overcome this barrier, we developed a synthetic-biology approach based on a technique known as codon shuffling. Computer-assisted algorithms redistribute codons in a helper gene, thereby eliminating regions of homology, while enabling manipulation of factors such as codon-pair bias and CpG content to effectively titrate helper-gene protein levels. We apply this technique to rescue the replication of a murine gammaherpesvirus engineered with a mutation in the major immediate-early transactivator protein RTA. Complementation with codon-shuffled RTA constructs did not yield any WT revertant virus, a sharp contrast to WT virus contamination frequently observed during complementation with an unmodified helper gene. We further demonstrate the importance of eliminating WT virus contamination in an animal model of gammaherpesvirus lethality. We propose complementation by codon shuffling as a means to produce replication-defective or attenuated viruses. This method has immediate utility for investigating roles of essential genes in viral replication and will better enable future development of herpesvirus vaccines.
Subject(s)
Codon/chemistry , Gammaherpesvirinae/genetics , Gene Expression Regulation, Viral , Genetic Engineering/methods , Helper Viruses/genetics , Immediate-Early Proteins/genetics , Trans-Activators/genetics , Algorithms , Animals , Base Pairing , Cell Line , Codon/metabolism , Female , Fibroblasts/virology , Gammaherpesvirinae/metabolism , HEK293 Cells , Helper Viruses/metabolism , Herpesviridae Infections/immunology , Herpesviridae Infections/prevention & control , Herpesviridae Infections/virology , Herpesvirus Vaccines/biosynthesis , Herpesvirus Vaccines/genetics , Homologous Recombination , Humans , Immediate-Early Proteins/immunology , Mice , Mice, SCID , Trans-Activators/immunology , Virus Replication/geneticsABSTRACT
A long-held dogma posits that strong presentation to the immune system of the dominant influenza virus glycoprotein antigens neuraminidase (NA) and hemagglutinin (HA) is paramount for inducing protective immunity against influenza virus infection. We have deliberately violated this dogma by constructing a recombinant influenza virus strain of A/PR8/34 (H1N1) in which expression of NA and HA genes was suppressed. We down-regulated NA and HA expression by recoding the respective genes with suboptimal codon pair bias, thereby introducing hundreds of nucleotide changes while preserving their codon use and protein sequence. The variants PR8-NA(Min), PR8-HA(Min), and PR8-(NA+HA)(Min) (Min, minimal expression) were used to assess the contribution of reduced glycoprotein expression to growth in tissue culture and pathogenesis in BALB/c mice. All three variants proliferated in Madin-Darby canine kidney cells to nearly the degree as WT PR8. In mice, however, they expressed explicit attenuation phenotypes, as revealed by their LD50 values: PR8, 32 plaque-forming units (PFU); HA(Min), 1.7 × 10(3) PFU; NA(Min), 2.4 × 10(5) PFU; (NA+HA)(Min), ≥3.16 × 10(6) PFU. Remarkably, (NA+HA)(Min) was attenuated >100,000-fold, with NA(Min) the major contributor to attenuation. In vaccinated mice (NA+HA)(Min) was highly effective in providing long-lasting protective immunity against lethal WT challenge at a median protective dose (PD50) of 2.4 PFU. Moreover, at a PD50 of only 147 or 237, (NA+HA)(Min) conferred protection against heterologous lethal challenges with two mouse-adapted H3N2 viruses. We conclude that the suppression of HA and NA is a unique strategy in live vaccine development.
Subject(s)
Down-Regulation/genetics , Hemagglutinin Glycoproteins, Influenza Virus/metabolism , Influenza A Virus, H1N1 Subtype , Neuraminidase/metabolism , Orthomyxoviridae Infections/prevention & control , Viral Vaccines/metabolism , Animals , Blotting, Northern , Blotting, Western , Cross Protection , Dogs , Lethal Dose 50 , Madin Darby Canine Kidney Cells , Male , Mice , Mice, Inbred BALB C , Orthomyxoviridae Infections/immunologyABSTRACT
Genomes of RNA viruses contain multiple functional RNA elements required for translation or RNA replication. We use unique approaches to identify functional RNA elements in the coding sequence of poliovirus (PV), a plus strand RNA virus. The general method is to recode large segments of the genome using synonymous codons, such that protein sequences, codon use, and codon pair bias are conserved but the nucleic acid sequence is changed. Such recoding does not affect the growth of PV unless it destroys the sequence/structure of a functional RNA element. Using genetic analyses and a method called "signal location search," we detected two unique functionally redundant RNA elements (α and ß), each about 75 nt long and separated by 150 nt, in the 3'-terminal coding sequence of RNA polymerase, 3D(pol). The presence of wild type (WT) α or ß was sufficient for the optimal growth of PV, but the alteration of both segments in the same virus yielded very low titers and tiny plaques. The nucleotide sequences and predicted RNA structures of α and ß have no apparent resemblance to each other. In α, we narrowed down the functional domain to a 48-nt-long, highly conserved segment. The primary determinant of function in ß is a stable and highly conserved hairpin. Reporter constructs showed that the α- and ß-segments are required for RNA replication. Recoding offers a unique and effective method to search for unknown functional RNA elements in coding sequences of RNA viruses, particularly if the signals are redundant in function.
Subject(s)
Computer-Aided Design , DNA-Directed RNA Polymerases/genetics , Genetic Engineering/methods , Poliovirus/genetics , RNA, Viral/genetics , Virus Replication/genetics , Poliovirus/growth & development , Protein Structure, Tertiary/geneticsABSTRACT
Adeno-associated virus (AAV) is a single-stranded parvovirus retaining the unique capacity for site-specific integration into a transcriptionally silent region of the human genome, a characteristic requiring the functional properties of the Rep 78/68 polypeptide in conjunction with AAV terminal repeat integrating elements. Previous strategies designed to assemble these genetic elements into adenoviral (Ad) backbones have been limited by the general intolerability of AAV Rep sequences, prompting us to computationally reengineer the Rep gene by using synonymous codon pair recoding. Rep mutants generated by using de novo genome synthesis maintained the polypeptide sequence and endonuclease properties of Rep 78, while dramatically enhancing Ad replication and viral titer yields, characteristics indistinguishable from adenovirus lacking coexpressed Rep. Parallel approaches using domain swaps encompassing WT and recoded genomic segments, coupled with iterative computational algorithms, collectively established that 3' cis-acting Rep genetic elements (and not the Rep 78 polypeptide) retain dominant-acting sequences inhibiting Ad replication. These data provide insights into the molecular relationships of AAV Rep and Ad replication, while expanding the applicability of synonymous codon pair reengineering as a strategy to effect phenotypic endpoints.
Subject(s)
Computational Biology/methods , Dependovirus/genetics , Genetic Vectors/genetics , Viral Proteins/genetics , Base Sequence , Codon/genetics , Dependovirus/physiology , Endonucleases/metabolism , Genes, Viral/genetics , HEK293 Cells , HeLa Cells , Humans , Mutation/genetics , Viral Proteins/metabolism , Virus Replication/physiologyABSTRACT
Despite existing vaccines and enormous efforts in biomedical research, influenza annually claims 250,000-500,000 lives worldwide, motivating the search for new, more effective vaccines that can be rapidly designed and easily produced. We applied the previously described synthetic attenuated virus engineering (SAVE) approach to influenza virus strain A/PR/8/34 to rationally design live attenuated influenza virus vaccine candidates through genome-scale changes in codon-pair bias. As attenuation is based on many hundreds of nucleotide changes across the viral genome, reversion of the attenuated variant to a virulent form is unlikely. Immunization of mice by a single intranasal exposure to codon pair-deoptimized virus conferred protection against subsequent challenge with wild-type (WT) influenza virus. The method can be applied rapidly to any emerging influenza virus in its entirety, an advantage that is especially relevant when dealing with seasonal epidemics and pandemic threats, such as H5N1- or 2009-H1N1 influenza.
Subject(s)
Computer-Aided Design , Orthomyxoviridae/immunology , Viral Vaccines , Animals , Cells, Cultured , Codon , Dogs , Genome, Viral , Lethal Dose 50 , Mice , Molecular Sequence Data , Orthomyxoviridae/geneticsABSTRACT
BACKGROUND: New short-read sequencing technologies produce enormous volumes of 25-30 base paired-end reads. The resulting reads have vastly different characteristics than produced by Sanger sequencing, and require different approaches than the previous generation of sequence assemblers. In this paper, we present a short-read de novo assembler particularly targeted at the new ABI SOLiD sequencing technology. RESULTS: This paper presents what we believe to be the first de novo sequence assembly results on real data from the emerging SOLiD platform, introduced by Applied Biosystems. Our assembler SHORTY augments short-paired reads using a trivially small number (5 - 10) of seeds of length 300 - 500 bp. These seeds enable us to produce significant assemblies using short-read coverage no more than 100x, which can be obtained in a single run of these high-capacity sequencers. SHORTY exploits two ideas which we believe to be of interest to the short-read assembly community: (1) using single seed reads to crystallize assemblies, and (2) estimating intercontig distances accurately from multiple spanning paired-end reads. CONCLUSION: We demonstrate effective assemblies (N50 contig sizes approximately 40 kb) of three different bacterial species using simulated SOLiD data. Sequencing artifacts limit our performance on real data, however our results on this data are substantially better than those achieved by competing assemblers.
Subject(s)
Computational Biology/methods , Sequence Analysis, DNA/methods , Base Sequence , Gene Expression Profiling , Genome, BacterialABSTRACT
As a result of the redundancy of the genetic code, adjacent pairs of amino acids can be encoded by as many as 36 different pairs of synonymous codons. A species-specific "codon pair bias" provides that some synonymous codon pairs are used more or less frequently than statistically predicted. We synthesized de novo large DNA molecules using hundreds of over-or underrepresented synonymous codon pairs to encode the poliovirus capsid protein. Underrepresented codon pairs caused decreased rates of protein translation, and polioviruses containing such amino acid-independent changes were attenuated in mice. Polioviruses thus customized were used to immunize mice and provided protective immunity after challenge. This "death by a thousand cuts" strategy could be generally applicable to attenuating many kinds of viruses.
Subject(s)
Capsid Proteins/genetics , Codon , Genome, Viral , Poliovirus Vaccines , Poliovirus/genetics , Poliovirus/pathogenicity , Algorithms , Animals , Antibodies, Viral/biosynthesis , Cloning, Molecular , Cytopathogenic Effect, Viral , HeLa Cells , Hot Temperature , Humans , Mice , Mice, Transgenic , Mutation , Poliomyelitis/immunology , Poliomyelitis/virology , Poliovirus/growth & development , Poliovirus/immunology , Poliovirus Vaccines/genetics , Poliovirus Vaccines/immunology , Protein Biosynthesis , Vaccination , Vaccines, Attenuated/genetics , Vaccines, Attenuated/immunology , Viral Plaque Assay , VirulenceABSTRACT
The effects of elevated atmospheric CO(2) (560 p.p.m.) and subsequent plant responses on the soil microbial community composition associated with trembling aspen was assessed through the classification of 6996 complete ribosomal DNA sequences amplified from the Rhinelander WI free-air CO(2) and O(3) enrichment (FACE) experiments microbial community metagenome. This in-depth comparative analysis provides an unprecedented, detailed and deep branching profile of population changes incurred as a response to this environmental perturbation. Total bacterial and eukaryotic abundance does not change; however, an increase in heterotrophic decomposers and ectomycorrhizal fungi is observed. Nitrate reducers of the domain bacteria and archaea, of the phylum Crenarchaea, potentially implicated in ammonium oxidation, significantly decreased with elevated CO(2). These changes in soil biota are evidence for altered interactions between trembling aspen and the microorganisms in its surrounding soil, and support the theory that greater plant detritus production under elevated CO(2) significantly alters soil microbial community composition.
Subject(s)
Archaea/isolation & purification , Bacteria/isolation & purification , Carbon Dioxide/metabolism , Fungi/isolation & purification , Soil Microbiology , Air Conditioning , Archaea/genetics , Archaea/metabolism , Atmosphere , Bacteria/genetics , Bacteria/metabolism , DNA, Archaeal/genetics , DNA, Bacterial/genetics , DNA, Fungal/genetics , DNA, Ribosomal/genetics , Ecosystem , Fungi/genetics , Molecular Sequence Data , Nitrates/metabolism , Polymerase Chain Reaction , Populus , Quaternary Ammonium Compounds/metabolism , Soil/analysisABSTRACT
To construct full-genome spotted microarrays, a large number of PCR primers that amplify the required DNA need to be synthesized. We describe an algorithmic technique that allows one to use fewer primers to achieve this goal. This can reduce the expense of constructing full-genome spotted microarrays considerably. PCR primers are usually designed, so that each primer occurs uniquely in the genome. This condition is unnecessarily strong for selective amplification, because only the primer pair associated with each amplification needs be unique. We also describe the interface to our software, MultiPrimer, that computes a small set of primers for amplification of a given gene set.
Subject(s)
DNA Primers/chemistry , Genome , Oligonucleotide Array Sequence Analysis , Polymerase Chain Reaction , Sequence Analysis, DNA , Software , DNA Primers/genetics , Genome/geneticsABSTRACT
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.
ABSTRACT
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.
Subject(s)
Codon/genetics , Poliomyelitis/genetics , Poliomyelitis/virology , Poliovirus/genetics , Poliovirus/pathogenicity , Protein Biosynthesis/genetics , Animals , Capsid Proteins/genetics , Capsid Proteins/metabolism , Enzyme-Linked Immunosorbent Assay , Genome, Viral/genetics , HeLa Cells , Humans , Membrane Proteins/genetics , Membrane Proteins/metabolism , Mice , Mice, Transgenic , Phenotype , Poliomyelitis/metabolism , Poliomyelitis/pathology , Receptors, Virus/genetics , Receptors, Virus/metabolism , Virulence/geneticsABSTRACT
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.
Subject(s)
Evolution, Molecular , Gene Conversion , Genes, Fungal , Saccharomyces cerevisiae/genetics , Base Sequence , Codon , DNA, Fungal , Exons , Gene Duplication , Genes, Duplicate , Genome, Fungal , Models, Genetic , Molecular Sequence Data , Sequence Homology, Nucleic AcidABSTRACT
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).
Subject(s)
Algorithms , RNA, Messenger , Selection, Genetic , Sequence Analysis, RNA/methods , Computational Biology/methods , Data Interpretation, Statistical , Evolution, Molecular , Nucleic Acid ConformationABSTRACT
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.
Subject(s)
Computational Biology/methods , Genetic Variation , Mutation , Sequence Analysis, DNA/methods , Algorithms , Data Interpretation, Statistical , Gene Frequency , Polymorphism, Single Nucleotide , Sequence DeletionABSTRACT
A substantial percentage of the expense in constructing full-genome spotted microarrays comes from the cost of synthesizing the PCR primers to amplify the desired DNA. We propose a computationally-based method to substantially reduce this cost. Historically, PCR primers are designed so that each primer occurs uniquely in the genome. This condition is unnecessarily strong for selective amplification, since only the primer pair associated with each amplification need be unique. We demonstrate that careful design in a genome-level amplification project permits us to save the cost of several thousand primers over conventional approaches.