Error Tree: A Tree Structure for Hamming and Edit Distances and Wildcards Matching

Abstract

Abstract

Approximate pattern matching is a fundamental problem in the bioinformatics and information retrieval applications. The problem involves different matching relations such as Hamming distance, edit distances, and the wildcards matching problem. The input is usually a text of length n over a fixed alphabet of length Σ, a pattern of length m, and an integer k. The output is to find all positions that have ≤ k Hamming distance, edit distance, or wildcards matching with P. Many algorithms and indexes have been proposed to solve the problems more efficiently, but due to the space and time complexities of the problems, most tools adopted heuristics approaches based on, for instance, suffix tree, suffix array, or Burrows Wheeler Transform to reach practical implementations.

Error Tree is a novel tree structure that is mainly oriented to solve the approximate pattern matching problems, using less space and faster computation time. The algorithm proposes for Hamming distance and wildcards matching a tree structure that needs \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$ \textbf{O} ( \textbf{n} \frac {{log_{\sum}^{k}} n} {K!})$$ \end{document} words and takes \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$ \textbf{O} \left( {\frac {m^{k}} {k!}} + \textbf{occ}\right) \left( \textbf{O} ( \textbf{m} + {\frac {log_{\sum}^{k}n} {k!}} + \textbf{occ}\right)$$ \end{document} in the average case) of query time for any online/offline pattern, where occ is the number of outputs. In addition, a tree structure of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$ \textbf{O} ( \textbf{2}^{k} \textbf{n} \frac {{log_{\sum}^{k}} n} {K!})$$ \end{document} words and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\textbf{\textit{O}}(\frac{\textbf{\textit{m}}^\textbf{\textit{k}}}{\textbf{\textit{k}}!}\hbox{+}\,{\bf 3}^\textbf{\textit{k}}\textbf{\textit{occ}})(\textbf{\textit{O}}(\textbf{\textit{m}}\hbox{+}\frac{\mathop\textbf{\textit{log}}_{\boldsymbol{\Sigma}}^\textbf{\textit{k}}\textbf{\textit{n}}}{\textbf{\textit{k}}!}\hbox{+}{\bf3}^\textbf{\textit{k}}\textbf{\textit{occ}})$$ \end{document} in the average case) query time for edit distance for any online/offline pattern.