A nonlinear measure of subalignment similarity and its significance levels
type: Item
instance of: scholarly article
title: A nonlinear measure of subalignment similarity and its significance levels
zbMATH Open document ID: 0606.92015
DOI: 10.1007/BF02462327
author: Stephen F. Altschul
author: Bruce W. Erickson
published in: Bulletin of Mathematical Biology
publication date: 1986-01-01T00:00:00Z
review text: A new measure of subalignment similarity is introduced. Specifically, similarity s(l,c) is defined as the logarithm to the base p of the probability of finding c or fewer mismatches in a subalignment of length l, where p is the probability of a match. Previous algorithms can not use this measure to find locally optimal subalignments because, unlike Needleman-Wunsch and Sellers similarities, this measure is nonlinear. A new pattern recognition algorithm is described for finding all locally optimal subalignments of two nucleotide sequences. The DD algorithm can use s(l,c) or any other reasonable similarity function to assess the relative interest of subalignments. The DD algorithm searches only the diagonal graph, which lacks insertions and deletions. This search strategy greatly decreases the computation time and does not require an arbitrary choice of gap cost. The paths of the resulting DD graph usually draw attention to likely locations for insertions and deletions. A heuristic formula is derived for estimating significance levels for s(l,c) in the context of the lengths of the two aligned sequences. The DD algorithm has been used to find interesting subalignments between the nucleotide sequences for human and murine interleukin 2.
Mathematics Subject Classification ID: 92Cxx
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68P10
zbMATH DE Number: 3980994
zbMATH Keywords: nonlinear measure
zbMATH Keywords: biochemistry
zbMATH Keywords: new measure of subalignment similarity
zbMATH Keywords: new pattern recognition algorithm
zbMATH Keywords: locally optimal subalignments of two nucleotide sequences
zbMATH Keywords: heuristic formula
zbMATH Keywords: estimating significance levels
zbMATH Keywords: DD algorithm
MaRDI profile type: Publication
Wikidata QID: Q68820504
cites work: Optimal sequence alignment using affine gap costs
cites work: Locally optimal subalignments using nonlinear similarity functions
cites work: Critical phenomena in sequence matching
cites work: An extreme value theory for sequence matching
cites work: An extreme value theory for long head runs
cites work: On the Theory and Computation of Evolutionary Distances
cites work: The theory and computation of evolutionary distances: Pattern recognition
cites work: Pattern recognition in genetic sequences by mismatch density
cites work: Comparison of biosequences
cites work: Some biological sequence metrics
full work available at URL: https://doi.org/10.1007/bf02462327
OpenAlex ID: W2049471110
description: scientific article; zbMATH DE number 3980994