Increasing radius search schemes for the most similar strings on the Burkhard-Keller tree

Abstract

In this work, search schemes are proposed for (he most strings similar to a given one, based on the Levenshtein directional distance (Levenshtein, 1966), working on a Burkhard-Keller structure (Burkhard and Keller, 1973; Nevalainen and Ka- tajainen, 1982), organized by the transposition-invariant distance (Santana et al., 1987), and using an increasing search radius as opposed to the decreasing search radius schemes (Santana et al., 1988). Some organization approaches are studied to find the best way to improve search performance. The test results are analyzed, comparing these approaches and the different search schemes.