A Generalized Erdös-Rényi Law for Sequence Analysis Problems

Laurie J. Heyer ()
Additional contact information
Laurie J. Heyer: University of Southern California

Methodology and Computing in Applied Probability, 2000, vol. 2, issue 3, 309-329

Abstract: Abstract We consider a class of random variables that includes scoring functions arising in computational molecular biology, such as sequence alignment and folding. We characterize the class by a set of properties, and show that, under certain conditions, such random variables follow an Erdös-Rényi law of large numbers. That is, $$\begin{gathered} _{\text{2}}^{\text{ + }} \hfill \\ \hfill \\ \mathop {\lim }\limits_{n \to \infty } \frac{{T_n }}{{\log n}} = sd{\text{ a}}{\text{.s}}{\text{.}} \hfill \\ \end{gathered} $$ where Tn is the maximum score over contiguous regions from each of s independent sequences, and d is a function of the large deviation rate of the scoring function. This result unifies several others, and applies to more general scoring systems on any number of sequences. We show how the theorem can be applied to a recently introduced scoring function. Finally, we conjecture that a modified form of this function behaves similarly, and support the conjecture with simulations.

Keywords: strong law; Erdös-Rényi law; sequence analysis; alignment; structural alignment (search for similar items in EconPapers)
Date: 2000
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1023/A:1010085313469 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:metcap:v:2:y:2000:i:3:d:10.1023_a:1010085313469

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/11009

DOI: 10.1023/A:1010085313469

Access Statistics for this article

Methodology and Computing in Applied Probability is currently edited by Joseph Glaz

More articles in Methodology and Computing in Applied Probability from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().