A fast word search algorithm for the representation of sequence similarity in genomic DNA
C. Lefèvre, J E Ikeda · Nucleic Acids Research · 1994
Nucleic Acids Research, 22, pp. 404–411 (1994) The Publisher's wish to apologize for incorrect presentation of the algorithm for this paper. The correct presentation is as follows: Match2trees (Nodel, Node2,k. m) if k = T then collect positions of occurrence of word w from the sub trees rooted at Nodel and Node2. return. if Nodel is a leaf then match (with at most MaxMisrnaich-m mismatches) the T-k symbols following the word represented by Nodel with sub tree rooted at Node2. return. if Node2 is a leaf then match (with at most MaxMismaich-m mismatches) the T-k symbols following the word represented by Node2 with sub tree rooted at Node I. return. for all edges leaving Nodel let Edgel be that edge. let NDI be the node this edge leads to. for all edges leaving Node2 let Edge2 be that edge. let CurrentMismatch be m. if the labels of Edge I and Edge2 are different let CurrentMismatch be m + I. if CurrentMismatch ≤ MaxMismatch let ND2 be the node Edge2 leads to. Match2trees (ND I, ND2, k + I, CurrentMismatch). return.