MissMax: alignment-free sequence comparison with mismatches through filtering and heuristics

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Sequence similarity measurement is crucial in bioinformatics.
• Alignment-free methods are fast but less accurate than alignment-based methods.
• Approximate matching is being integrated to improve alignment-free similarity measures.

Purpose of the Study:

• To present MissMax, an exact algorithm for computing the longest common substring with mismatches.
• To enable more accurate sequence similarity measures using approximate matches.
• To offer a faster, precise "relaxed" version of the MissMax algorithm.

Main Methods:

• Developed an exact algorithm (MissMax) for longest common substring with k mismatches.
• Utilized suffix comparisons for calculating common substring statistics.
• Implemented a "relaxed" version for improved practical speed.

Main Results:

• MissMax accurately computes longest common substrings with mismatches.
• The algorithm facilitates calculation of longest and average common substrings with k mismatches.
• The relaxed MissMax version offers practical speed improvements with high precision.

Conclusions:

• MissMax enhances alignment-free sequence similarity analysis.
• The algorithm provides a valuable tool for bioinformatics research.
• Approximate matching strategies effectively bridge the accuracy gap in sequence comparison.