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

Area of Science:

• Computational Biology
• Computer Science
• Data Structures

Background:

• Approximate pattern matching is crucial for bioinformatics and information retrieval.
• Existing algorithms face challenges with space and time complexity, often relying on heuristic approaches.
• Problems include Hamming distance, edit distance, and wildcard matching.

Purpose of the Study:

• To introduce a novel tree structure, the Error Tree, for efficient approximate pattern matching.
• To improve upon existing algorithms in terms of space and time complexity.
• To provide a unified solution for various approximate matching problems.

Main Methods:

• Development of the Error Tree data structure.
• Analysis of space and query time complexities for different matching types.
• Implementation and evaluation of the Error Tree for Hamming distance, wildcard matching, and edit distance.

Main Results:

• The Error Tree requires O(n) words of space.
• Achieves O(k + occ) average query time for Hamming distance and wildcard matching.
• Provides O(k + occ) average query time for edit distance.

Conclusions:

• The Error Tree offers a more efficient solution for approximate pattern matching problems.
• It demonstrates reduced space and faster computation compared to existing methods.
• This structure has significant implications for bioinformatics and information retrieval applications.