A CGM-Based Parallel Algorithm Using the
Four-Russians Speedup for the 1-D Sequence
Alignment Problem

Jerry Lacmou Zeutouo* — Grace Colette Tessa Masse* — Franklin Ingrid
Kamga Youmbi*
* Department of Mathematics and Computer Science
Faculty of Science, University of Dschang
PO Box 67, Dschang-Cameroon

ABSTRACT. The CGM model is one of the most widely used models for the design of parallel algorithms. It has shown its efficiency in solving several problems modeled by dynamic programming such as the longest common subsequence problem, which is a special case of the one-dimensional sequence alignment problem. This problem consists in aligning two strings of length n to measure their similarity. It is widely used in many fields, particularly in Bioinformatics where n is usually very large. Brubach and Ghurye proposed a sequential solution based on the Four-Russians speed-upthat requires O(n2= log n) execution time. To the best of our knowledge, there are not yet parallel solutions on the CGM model to solve this problem. This paper is exclusively dedicated to this task. Our solution applies to both local and global similarity computations and is based on Brubach and Ghurye’s sequential algorithm. It requires O(n2=p log n) execution time with O(p) communication rounds on p processors.

RÉSUMÉ. Le modèle CGM est l’un des modèles les plus utilisés pour la conception d’algorithmes parallèles. Il a montré son efficacité pour la résolution de plusieurs problèmes modélisés par la programmation dynamique comme le problème de la plus longue sous-séquence commune, qui est un  cas particulier du problème d’alignement de séquence à une dimension. Ce problème consiste à aligner deux chaînes de longueur n afin de mesurer leur similarité. Il est largement utilisé dans de nombreux domaines, en particulier dans la Bio-informatique où n est généralement très grand. Brubach et Ghurye ont proposé une solution séquentielle basée sur l’accélération de Four-Russians qui nécessite un temps d’exécution de O(n2= log n). À notre connaissance, il n’existe pas encore de solutions parallèles sur le modèle CGM pour la résolution de ce problème. Ce papier est exclusivement dédié à cette tâche. Notre solution s’applique aux calculs de similarité locaux et globaux, et est basée sur l’algorithme séquentiel de Brubach et Ghurye. Elle nécessite un temps d’exécution de O(n2=p log n) avec O(p) rondes de communication sur p processeurs.

KEYWORDS : parallel algorithm, CGM model, dynamic programming, sequence alignment, Four- Russians

MOTS-CLÉS : algorithme parallèle, modèle CGM, programmation dynamique, alignement de séquences, Four-Russians.

Video short presentation