String-matching and alignment algorithms for finding motifs in NGS data

The development of high-throughput Next Generation Sequencing (NGS) technologies allows to massively extract at low cost an extremely large amount of biological sequences in the form of reads, i.e., short fragments of an organism’s genome. The advent of NGS poses new issues for computer scientists and bioinformaticians, leading to the design of algorithms for aligning and merging the reads in order to obtain an efficient and effective reconstruction of the genome. In this chapter, we focus on methods that can quickly and precisely establish whether two reads are similar or not and that allow to analyze biological sequences extracted with NGS technologies. In particular, the most widespread string-matching, alignment-based, and alignment-free algorithms are summarized and discussed.