摘要:

ABSTRACTWe consider molecular models for computing and derive a DNA-based mechanism for solving intractable problems through massive parallelism. In principle, such methods might reduce the effort needed to solve otherwise difficult tasks, such as factoring large numbers, a computationally intensive task whose intractability forms the basis for much of modern cryptography.Key words:DNA; nanotechnology; recombination; site-directed mutagenesis; intractability; combinatorial search; NP-completeness

ISSN:1066-5277    

DOI:10.1089/cmb.1995.2.1

年代:1995

数据来源: MAL

摘要:

ABSTRACTWe introduce a maximum discrimination method for building hidden Markov models (HMMs) of protein or nucleic acid primary sequence consensus. The method compensates for biased representation in sequence data sets, superseding the need for sequence weighting methods. Maximum discrimination HMMs are more sensitive for detecting distant sequence homologs than various other HMM methods or BLAST when tested on globin and protein kinase catalytic domain sequences.Key words:hidden Markov model; database searching; sequence consensus; sequence weighting

ISSN:1066-5277    

DOI:10.1089/cmb.1995.2.9

年代:1995

数据来源: MAL

摘要:

ABSTRACTA method is presented for determining within strict bounds the probability of matching a regular expression with a match start point in a given section of a random data string. The method in general requires time and space exponential in the number of optional characters in the regular expression, but in practice was used to determine bounds for probabilities of matching all the ProSite patterns without difficulty.

ISSN:1066-5277    

DOI:10.1089/cmb.1995.2.25

年代:1995

数据来源: MAL

摘要:

ABSTRACTWe present an efficient algorithm for scoring clones given an ordering of probes under a schema proposed by Alizadehet al.(1994) in the context of physical mapping with unique probes. The algorithm runs in time linear in the number of blocks of ones in the underlying sparse incidence matrix. A sparse and efficient algorithm for this task is important as it appears to be a central task in most algorithms for physical mapping.

ISSN:1066-5277    

DOI:10.1089/cmb.1995.2.33

年代:1995

数据来源: MAL

摘要:

ABSTRACTLinear invariants are useful tools for testing phylogenetic hypotheses from aligned DNA/ RNA sequences, particularly when the sites evolve at different rates. Here we give a simple, graph theoretic classification for each phylogenetic treeT, of its associated vector spaceI(T) of linear invariants under the Jukes–Cantor one-parameter model of nucleotide substitution. We also provide an easily described basis forI(T), and show that ifTis a binary (fully resolved) phylogenetic tree withnsequences at its leaves then: dim[I(T)] = 4n−F2n−2whereFnis thenth Fibonacci number. Our method applies a recently developed Hadamard matrix-based technique to describe elements ofI(T) in terms of edge-disjoint packings of subtrees inT, and thereby complements earlier more algebraic treatments.Key words:Phylogenetic invariants; trees; forests; Hadamard matrix; Jukes–Cant

ISSN:1066-5277    

DOI:10.1089/cmb.1995.2.39

年代:1995

数据来源: MAL

摘要:

ABSTRACTWe introduce a mathematical model to treat the polymerase chain reaction (PCR), where we regard the accumulation of new molecules during a PCR cycle as a randomly bifurcating tree. This model enables us to compute an approximate formula for the distribution of the number of replications that have occurred between a pair of molecules, which depends on the efficiency λ of the reaction, the numberN0of template molecules at the beginning of the PCR and the numbercof PCR cycles. The reliability of the approximation is tested by computer simulations. Finally, to model the effect of the intrinsic error rate of the polymerase, we superimpose a substitution process on the tree. The resulting closed formula for the distribution of pairwise differences of sequences as a function of error rate μ and efficiency λ can be used to estimate the error rate, if λ is known.Key words:polymerase chain reaction; distribution of pairwise differences; error rate; efficiency; random trees; simulating

ISSN:1066-5277    

DOI:10.1089/cmb.1995.2.49

年代:1995

数据来源: MAL

摘要:

ABSTRACTWe construct a mathematical model for the polymerase chain reaction and its mutations using the theory of branching processes. Under this model we study the number of mutations in a randomly chosen sequence afternPCR cycles. A method for estimating the mutation is proposed and the variance of this estimator is studied. We also study the distribution of the Hamming distance between two randomly chosen sequences and a method for estimating the mutation rate based on pairwise differences is proposed.Key words:PCR; branching processes; estimation; pairwise difference; polymerase chain reaction

ISSN:1066-5277    

DOI:10.1089/cmb.1995.2.63

年代:1995

数据来源: MAL

摘要:

ABSTRACTRecognition of function of newly sequenced DNA fragments is an important area of computational molecular biology. Here we present an extensive review of methods for prediction of functional sites, tRNA, and protein-coding genes and discuss possible further directions of research in this area.Key words:DNA sequence analysis; functional sites; genes; protein-coding regions; exons; introns; prediction; tRNA

ISSN:1066-5277    

DOI:10.1089/cmb.1995.2.87

年代:1995

数据来源: MAL

摘要:

ABSTRACTThe length of an open reading frame (ORF) is one important piece of evidence often used in locating new genes, particularly in organisms where splicing is rare. However, there have been no systematic studies quantifying the degree of correlation between length of ORF, on the one hand, and likelihood of gene function, on the other. In this paper, techniques are derived to estimate the conditional probability of gene function, given ORF length, based on evidence both from the databases and from simulation. Several complete chromosomes ofSaccharomyces cerevisiaehave now been sequenced, and considerable effort is being expended on locating and characterizing the genes in these sequences. Thus, we illustrate the techniques for this organism.Key words:open reading frame; gene identification; gene finding; yeast chromosome sequence

ISSN:1066-5277    

DOI:10.1089/cmb.1995.2.117

年代:1995

数据来源: MAL

摘要:

ABSTRACTThe identification of protein sequences that fold into certain known three-dimensional (3D) structures, or motifs, is evaluated through a probabilistic analysis of their one-dimensional (1D) sequences. We present a correlation method that runs in linear time and incorporates pairwise dependencies between amino acid residues at multiple distances to assess the conditional probability that a given residue is part of a given 3D structure. This method is generalized to multiple motifs, where a dynamic programming approach leads to an efficient algorithm that runs in linear time for practical problems. By this approach, we were able to distinguish (2-stranded) coiled-coil from non-coiled-coil domains and globins from nonglobins. When tested on the Brookhaven X-ray crystal structure database, the method does not produce any false-positive or false-negative predictions of coiled coils.Key words:profile analysis; protein structure prediction; protein folding; coiled coil; globin

ISSN:1066-5277    

DOI:10.1089/cmb.1995.2.125

年代:1995

数据来源: MAL