Pattern recognition in genetic sequences by mismatch density

DOI10.1007/BF02459499MaRDI QIDQ1070960zbMATH OpenOpenAlexFDO

Authors Peter H. Sellers

Publication date 1984

Published in Bulletin of Mathematical Biology (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02459499

zbMATH Keywords

algorithmalignmentdegree of mismatchdegree of similaritydynamic programmingexamplesgenetic sequencespattern similarity

Mathematics Subject Classification ID

Computational methods for problems pertaining to biology (92-08) Genetics and epigenetics (92D10)

Review text

The main object of this paper is to formalize the concept of pattern similarity in genetic sequences and to give an algorithm which finds all such similarities in a given context: Consider two genetic sequences, represented by strings of symbols \(a_ 1...a_ m\) and \(b_ 1...b_ n\), respectively. A pair of segments \(a_ p...a_ q\) and \(b_ r...b_ s\) out of these sequences, aligned in such a way as to exhibit their similarity, is called an alignment. For an alignment A the length l(A) is defined as the average length of the two segments, and the degree of mismatch d(A) is defined via the minimum number of mutations and deletions needed to make the two identical. Then the degree of similarity between the two segments of alignment A is measured by \(r\cdot l(A)-d(A)\), where r is a positive proportionality constant. The algorithm presented in this paper checks for all alignments between any segment from one sequence and any segment from another and finds every alignment A such that the function \(r\cdot l(A)-d(A)\) is a maximum in the neighbourhood of A. Moreover, the method is extensively illustrated by means of several examples.

Recommendations

• Pattern recognition in several sequences: Consensus and alignment
• scientific article; zbMATH DE number 3898657
• Publication:4731047
• A nonlinear measure of subalignment similarity and its significance levels
• Efficient algorithms for molecular sequence analysis.

Cites work

• An algorithm for the distance between two finite sequences
• An extreme value theory for long head runs
• On the Theory and Computation of Evolutionary Distances
• The theory and computation of evolutionary distances: Pattern recognition

Cited in

(13)

• A nonlinear measure of subalignment similarity and its significance levels
• Locally optimal subalignments using nonlinear similarity functions
• Significance levels for biological sequence comparison using non-linear similarity functions
• Pattern analysis of the genetic code
• Approximate matching of regular expressions
• A time-efficient, linar-space local similarity algorithm
• Linear-time algorithms for computing maximum-density sequence segments with bioinformatics applications
• Efficient algorithms for locating the length-constrained heaviest segments with applications to biomolecular sequence analysis.
• Linear-space algorithms that build local alignments from fragments
• A metric approach for comparing DNA sequences
• scientific article; zbMATH DE number 3898657 (Why is no real title available?)
• scientific article; zbMATH DE number 6271723 (Why is no real title available?)
• Approximate periods of strings

This page was built for publication: Pattern recognition in genetic sequences by mismatch density

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1070960)