Анализ эффективности суффиксных деревьев для решения некоторых задач биоинформатики

The article presents the results of experimental study of the efficiency of using suffix trees for solving various problems of genomic sequence analysis. A software module based on the original implementation of suffix trees was used as a tool for study. We have developed procedures for solving the following problems: motif discovery, pattern search in a set of sequences, search for palindromes. For each problem we have compared the performance of the procedures on inputs of various sizes. Three variants of procedures have been compared for each problem: 1) based on ordinary suffix tree; 2) based on pruned suffix trees and 3) naive algorithm that does not use suffix trees. The results of the study have shown that for problems that require multiple comparisons of various strings with the same string (eg motif discovery and pattern search) suffix trees give significant performance gains. However, for single string analysis (palindrome search) naive approach is more efficient.