Approximate Circular Pattern Matching
- Friday, April 16, 2021 from 3:00pm to 4:00pm
Different variations of pattern matching problems have been studied extensively throughout the last two decades resulting in various breakthroughs. This Bibliographic Report focuses on the circular pattern matching problem and its variations. This problem is useful in the computational Biology context where one wants to compute occurrences of circular DNA patterns in a linear DNA sequence. However, due to errors introduced in wet-lab sequencing platforms, we have to deal with mismatches when matching the pattern against the input string. Thus, it is necessary to look into the approximate version of the circular pattern matching problem. Most of the solutions to this problem can be divided into two main approaches- Filtering based and non-filtering based algorithms under hamming distance and edit distance models. This report focuses on different approaches to solving this problem and several areas where we can improve these solutions.
- Gianforte School of Computing