HEURISTICALLY GUIDED SEARCH AND CHROMOSOME MATCHING,

Heuristically guided search is a technique which takes systematically into account information from the problem domain for directing the search. The problem is to find the shortest path in a weighted graph from a start vertex Va to a goal vertex Vz for every intermediate vertex, an estimate is available of the distance to Vz. If this estimate satisfies a consistency assumption, an algorithm by Hart, Nilsson and Raphael is guaranteed to find the optimum, looking at the a priori minimum number of vertices. A version of the above algorithm is presented, which is guaranteed to succeed with the minimum amount of storage. An application of this technique to the chromosome matching problem is then shown. Matching is the last stage of automatic chromosome analysis procedures, and can also solve ambiguities in the classification stage. Some peculiarities of this kind of data suggest the use of an heuristically guided search algorithm instead of the standard Edmonds algorithm. The method obtained in this way is proved to exploit the clustering of chromosome data a linear-quadratic dependence from the number of chromosomes is obtained for perfectly cluster data. Finally, some experimental results are given. Author