Computational complexity of algorithms for sequence comparison, short-read assembly and genome alignment
Version: 1,
Uploaded by: Administrator,
Date Uploaded:
25 November 2022
Warning
You are about to be redirected to a website not operated by the Mauritius Research and Innovation Council. Kindly note that we are not responsible for the availability or content of the linked site. Are you sure you want to leave this page?
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.
