Prediction of gene function: homology searches
Given a nucleotide or DNA sequence, searching the data
base(s) for similar sequences is known as “homology
searches”. This is essentially the task of finding all (local)
alignments between the data base of length n and a query
sequence of length m. The most popular software tool for
performing these searches is called BLAST; therefore
biologists often speak of “BLAST searches”. It is a
heuristic algorithm with average running time O(n),
independently of the length of the query sequence.