ETD

• sequence alignment
• seth

The Pattern Matching in Labeled Graphs (PMLG) problem consists in finding a match for a string that can spread among several nodes of a graph labeled with other strings. The goal of this thesis is to provide a formal proof of a conditional lower bound for such problem. The problem has been studied since 1992 and has recently received more and more consideration thanks to biology. Due to the rising of the NGS (Next-Generation Sequencing) techniques the study of the genome has experienced a drastic growth during the last years producing a large amount of data that needs to be managed. Thus, new algorithmic theories and tools has to be provided in order to meet these requests. Although the problem has been studied for quite a long time, finding an efficient solution in both the practical and theoretical fields still is an open challenge. One issue that has not been clarified yet is whether the algorithms that have been proposed heretofore are optimal or not.