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

The development of Next Generation Sequencing (NGS) technologies allows the extraction at low cost of an extremely large amount of biological sequences in the form of reads, i.e., short fragments of an organism's genome. The length of such reads is very small when compared to the length of a whole genome: it may range from 40 to 1000 base pairs (bp), i.e., characters, while the length of a simple genome (e.g., bacteria) is in the order of Megabase pairs (Mbp). Four main NGS technologies are currently used Eisenstein (Nat Biotechnol 30:1023- 1026, 2012): Roche 454, Illumina, Pacific Bioscience, and Ion Torrent.