An improved consensus algorithm for approximate string matching

Abstract

One of the fundamental tasks in bioinformatics consists in searching for patterns, in a protein or DNA sequence, that are sufficiently similar to a given motif. This problem is known as approximate string matching (ASM) and has several applications besides bioinformatics. The similarity between strings of symbols is typically evaluated by metrics such as the Hamming distance, the Levensthein distance, or correlation or consensus techniques. In this paper, a refinement of a recently introduced consensus algorithm is proposed and evaluated with real protein sequences from plants. Preliminary tests with real protein sequences from plants show that the proposed refinement can significantly increase the localization accuracy by up to 95%, while further reducing the number of false positives by around 80%. Thus, the proposed algorithm could be a useful tool in many biological applications.