A Survey on Sequence Alignment Algorithms and State-of-the-Art Aligners

Vast amounts of genomic, proteomic, transcriptomics and other forms, commonly referred to as -omics data, are generated daily in an unprecedented way thanks to high-throughput Next Generation Sequencing technologies. One of the main processes to generate value and insights from this data in bioinformatics is “sequence alignment”, an algorithmic routine that matches a “reference” sequence to a larger sequence. Despite the plethora of approaches, pairwise and multiple sequence alignment remain a complex problem that requires high computational power. In this paper, the most prominent sequence alignment approaches of the past three decades are reviewed and categorized, examining different aspects, such as their overall algorithmic synthesis, alignment quality and performance benchmarking tests in a uniform way. The latest trends reveal an increased specialization on biology-based directions, the need for alternative heuristic approaches and a promise in optics-enabled approaches and the quantum computing paradigm shift.