CYCLIC SEQUENCE ALIGNMENTS: APPROXIMATE VERSUS OPTIMAL TECHNIQUES
Ramón A. Mollineda, Enrique Vidal, Francisco Casacuberta · International Journal of Pattern Recognition and Artificial Intelligence · 2002
The problem of cyclic sequence alignment is considered. Most existing optimal methods for comparing cyclic sequences are very time consuming. For applications where these alignments are intensively used, optimal methods are seldom a feasible choice. The alternative to an exact and costly solution is to use a close-to-optimal but cheaper approach. In previous works, we have presented three suboptimal techniques inspired on the quadratic-time suboptimal algorithm proposed by Bunke and Bühler. Do these approximate approaches come sufficiently close to the optimal solution, with a considerable reduction in computing time? Is it thus worthwhile investigating these approximate methods? This paper shows that approximate techniques are good alternatives to optimal methods.