Dynamic programming algorithms for discovery of antibiotic resistance in microbial genomes

Manal Helal, Vitali Sintchenko

Research output: Contribution to journalArticlepeer-review


The translation of comparative genomics into clinical decision support tools often depends on the quality of sequence alignments. However, currently used methods of multiple sequence alignments suffer from significant biases and problems with aligning diverged sequences. The objective of this study was to develop and test a new multiple sequence alignment (MSA) algorithm suitable for the high-throughput comparative analysis of different microbial genomes. This algorithm employs an innovative tensor indexing method for partitioning the dynamic programming hyper-cube space for parallel processing. We have used the clinically relevant task of identifying regions that determine resistance to antibiotics to test the new algorithm and to compare its performance with existing MSA methods. The new method "mmDst" performed better than existing MSA algorithms for more divergent sequences because it employs a simultaneous alignment scoring recurrence, which effectively approximated the score for edge missing cell scores that fall outside the scoring region.

Original languageEnglish
Article numbere10
JournalElectronic Journal of Health Informatics (eJHI)
Issue number1
Publication statusPublished - 2011


  • Antibiotic resistance
  • Bioinformatics
  • Decision support systems
  • Dynamic programming
  • High performance computing
  • Tensor computing


Dive into the research topics of 'Dynamic programming algorithms for discovery of antibiotic resistance in microbial genomes'. Together they form a unique fingerprint.

Cite this