Dataset Information

Exact calculation of distributions on integers, with application to sequence alignment.

ABSTRACT: Computational biology is replete with high-dimensional discrete prediction and inference problems. Dynamic programming recursions can be applied to several of the most important of these, including sequence alignment, RNA secondary-structure prediction, phylogenetic inference, and motif finding. In these problems, attention is frequently focused on some scalar quantity of interest, a score, such as an alignment score or the free energy of an RNA secondary structure. In many cases, score is naturally defined on integers, such as a count of the number of pairing differences between two sequence alignments, or else an integer score has been adopted for computational reasons, such as in the test of significance of motif scores. The probability distribution of the score under an appropriate probabilistic model is of interest, such as in tests of significance of motif scores, or in calculation of Bayesian confidence limits around an alignment. Here we present three algorithms for calculating the exact distribution of a score of this type; then, in the context of pairwise local sequence alignments, we apply the approach so as to find the alignment score distribution and Bayesian confidence limits.

SUBMITTER: Newberg LA

PROVIDER: S-EPMC2858568 | biostudies-literature | 2009 Jan

REPOSITORIES: biostudies-literature

ACCESS DATA

Publications

Exact calculation of distributions on integers, with application to sequence alignment.

Newberg Lee A LA Lawrence Charles E CE

Journal of computational biology : a journal of computational molecular cell biology 20090101 1

Computational biology is replete with high-dimensional discrete prediction and inference problems. Dynamic programming recursions can be applied to several of the most important of these, including sequence alignment, RNA secondary-structure prediction, phylogenetic inference, and motif finding. In these problems, attention is frequently focused on some scalar quantity of interest, a score, such as an alignment score or the free energy of an RNA secondary structure. In many cases, score is natur ...[more]

PMID: 19119992

Similar Datasets

Project description:BACKGROUND:cis-Regulatory modules (CRMs) of eukaryotic genes often contain multiple binding sites for transcription factors. The phenomenon that binding sites form clusters in CRMs is exploited in many algorithms to locate CRMs in a genome. This gives rise to the problem of calculating the statistical significance of the event that multiple sites, recognized by different factors, would be found simultaneously in a text of a fixed length. The main difficulty comes from overlapping occurrences of motifs. So far, no tools have been developed allowing the computation of p-values for simultaneous occurrences of different motifs which can overlap. RESULTS:We developed and implemented an algorithm computing the p-value that s different motifs occur respectively k1, ..., ks or more times, possibly overlapping, in a random text. Motifs can be represented with a majority of popular motif models, but in all cases, without indels. Zero or first order Markov chains can be adopted as a model for the random text. The computational tool was tested on the set of cis-regulatory modules involved in D. melanogaster early development, for which there exists an annotation of binding sites for transcription factors. Our test allowed us to correctly identify transcription factors cooperatively/competitively binding to DNA. METHOD:The algorithm that precisely computes the probability of simultaneous motif occurrences is inspired by the Aho-Corasick automaton and employs a prefix tree together with a transition function. The algorithm runs with the O(n|Sigma|m|H| + K|sigma|K) Piiki) time complexity, where n is the length of the text |Sigma| is the alphabet size, m is the maximal motif length, |H| is the total number of words in motifs, K is the order of Markov model, and ki is the number of occurrences of the ith motif. CONCLUSION:The primary objective of the program is to assess the likelihood that a given DNA segment is CRM regulated with a known set of regulatory factors. In addition, the program can also be used to select the appropriate threshold for PWM scanning. Another application is assessing similarity of different motifs. AVAILABILITY:Project web page, stand-alone version and documentation can be found at http://bioinform.genetika.ru/AhoPro/

Dataset Information

Exact calculation of distributions on integers, with application to sequence alignment.

Publications

Exact calculation of distributions on integers, with application to sequence alignment.

Similar Datasets

OmicsDI is part of the ELIXIR infrastructure

Tweets