title: Computational complexity of algorithms for sequence comparison, short-read assembly and genome alignment.
abstract: A multitude of algorithms for sequence comparison, short-read assembly and whole-genome alignment have been developed in the general context of molecular biology, to support technology development for high-throughput sequencing, numerous applications in genome biology and fundamental research on comparative genomics. The computational complexity of these algorithms has been previously reported in original research papers, yet this often neglected property has not been reviewed previously in a systematic manner and for a wider audience. We provide a review of space and time complexity of key sequence analysis algorithms and highlight their properties in a comprehensive manner, in order to identify potential opportunities for further research in algorithm or data structure optimization. The complexity aspect is poised to become pivotal as we will be facing challenges related to the continuous increase of genomic data on unprecedented scales and complexity in the foreseeable future, when robust biological simulation at the cell level and above becomes a reality.
authors.affiliation: Department of Computer Science & Engineering, University of Mauritius, Réduit 80837, Mauritius. Electronic address: shakunb@uom.ac.mu.
authors.forename: Shakuntala
authors.initials: S
authors.lastname: Baichoo
authors.affiliation: Biological Computation & Process Laboratory, Chemical Process & Energy Resources Institute, Centre for Research & Technology Hellas, Thessalonica 57001, Greece. Electronic address: ouzounis@certh.gr.
authors.forename: Christos A
authors.initials: CA
authors.lastname: Ouzounis
mesh_terms: D000465:Algorithms; D000818:Animals; D019295:Computational Biology; D016678:Genome; D023281:Genomics; D006801:Humans; D016415:Sequence Alignment; D017422:Sequence Analysis, DNA
keywords: Bioinformatics algorithms; Computational complexity; Genome alignment; Sequence comparison; Short-read assembly