title: Estimating statistical significance of sequence alignments.
abstract: Algorithms that compare two proteins or DNA sequences and produce an alignment of the best matching segments are widely used in molecular biology. These algorithms produce scores that when comparing random sequences of length n grow proportional to n or to log(n) depending on the algorithm parameters. The Azuma-Hoeffding inequality gives an upper bound on the probability of large deviations of the score from its mean in the linear case. Poisson approximation can be applied in the logarithmic case.
authors: Department of Mathematics, University of Southern California, Los Angeles 90089-1113.
authors: M
authors: M
authors: Waterman
mesh_terms: D000465:Algorithms; D004247:DNA / Q000737:chemistry* / Q000235:genetics; D015233:Models, Statistical; D008967:Molecular Biology / Q000379:methods; D016012:Poisson Distribution; D011506:Proteins / Q000737:chemistry* / Q000235:genetics; D017386:Sequence Homology, Amino Acid; D012689:Sequence Homology, Nucleic Acid
chemical_list: D011506:Proteins; D004247:DNA