Skip to Main content Skip to Navigation
Conference papers

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

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-up that requires O(n^2 / 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(n^2 / p log n) execution time with O(p) communication rounds on p processors.
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download
Contributor : Jerry Lacmou Zeutouo Connect in order to contact the contributor
Submitted on : Monday, August 31, 2020 - 1:20:44 AM
Last modification on : Friday, September 4, 2020 - 4:38:36 PM
Long-term archiving on: : Tuesday, December 1, 2020 - 12:05:42 PM


Files produced by the author(s)


  • HAL Id : hal-02925791, version 1



Jerry Lacmou Zeutouo, Grace Colette Tessa Masse, Franklin Ingrid Kamga Youmbi. A CGM-Based Parallel Algorithm Using the Four-Russians Speedup for the 1-D Sequence Alignment Problem. CARI 2020 - Colloque Africain pour la Recherche en Informatique et Mathématiques Appliquées, Oct 2020, Thiès, Senegal. ⟨hal-02925791⟩



Les métriques sont temporairement indisponibles