Brona Brejova, Daniel G. Brown, Tomas Vinar .
**Optimal DNA signal recognition models with a fixed amount of intrasignal dependency**.
In G. Benson, R. Page, ed.,
*Algorithms and Bioinformatics: 3rd International Workshop (WABI)*,
2812 volume of *Lecture Notes in Bioinformatics*,
pp. 78-94, Budapest, Hungary, September 2003. Springer.

**Download preprint:** 03wabi-signals.ps.gz, 111Kb

**Download from publisher:** http://springerlink.metapress.com/link.asp?id=km0bdqw3mjk46lpt

**Related www page:** not available

**Bibliography entry:**
BibTeX

**See also:** early version

**Abstract:**

We study new probabilistic models for signals in DNA. Our models allow dependencies between multiple non-adjacent positions, in a generative model we call a higher-order tree. Computing the model of maximum likelihood is equivalent in our context to computing a minimum directed spanning hypergraph, a problem we show is NP-complete. We instead compute good models using simple greedy heuristics. In practice, the advantage of using our models over more standard models based on adjacent positions is modest. However, there is a notable improvement in the estimation of the probability that a given position is a signal, which is useful in the context of probabilistic gene finding. We also show that there is little improvement by incorporating multiple signals involved in gene structure into a composite signal model in our framework, though again this gives better estimation of the probability that a site is an acceptor site signal.

Last update: 10/01/2006