Parallelizing optimal multiple sequence alignment by dynamic programming

Manal Helal; Hossam El-Gindy; Lenore Mullin; Bruno Gaeta

doi:10.1109/ISPA.2008.93

Parallelizing optimal multiple sequence alignment by dynamic programming

Manal Helal, Hossam El-Gindy, Lenore Mullin, Bruno Gaeta

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Optimal multiple sequence alignment by dynamic programming, like many highly dimensional scientific computing problems, has failed to benefit from the improvements in computing performance brought about by multi-processor systems, due to the lack of suitable scheme to manage partitioning and dependencies. A scheme for parallel implementation of the dynamic programming multiple sequence alignment is presented, based on a peer to peer design and a multidimensional array indexing method. This design results in up to 5-fold improvement compared to a previously described master/slave design, and scales favourably with the number of processors used. This study demonstrates an approach for parallelising multi-dimensional dynamic programming and similar algorithms utilizing multi-processor architectures.

Original language	English
Title of host publication	Proceedings of the 2008 International Symposium on Parallel and Distributed Processing with Applications, ISPA 2008
Pages	669-674
Number of pages	6
DOIs	https://doi.org/10.1109/ISPA.2008.93
Publication status	Published - 2008
Externally published	Yes
Event	2008 International Symposium on Parallel and Distributed Processing with Applications, ISPA 2008 - Sydney, NSW, Australia Duration: 10 Dec 2008 → 12 Dec 2008

Publication series

Name	Proceedings of the 2008 International Symposium on Parallel and Distributed Processing with Applications, ISPA 2008

Conference

Conference	2008 International Symposium on Parallel and Distributed Processing with Applications, ISPA 2008
Country/Territory	Australia
City	Sydney, NSW
Period	10/12/08 → 12/12/08

Access to Document

10.1109/ISPA.2008.93

Cite this

Helal, M., El-Gindy, H., Mullin, L., & Gaeta, B. (2008). Parallelizing optimal multiple sequence alignment by dynamic programming. In Proceedings of the 2008 International Symposium on Parallel and Distributed Processing with Applications, ISPA 2008 (pp. 669-674). Article 4725210 (Proceedings of the 2008 International Symposium on Parallel and Distributed Processing with Applications, ISPA 2008). https://doi.org/10.1109/ISPA.2008.93

Helal, Manal ; El-Gindy, Hossam ; Mullin, Lenore et al. / Parallelizing optimal multiple sequence alignment by dynamic programming. Proceedings of the 2008 International Symposium on Parallel and Distributed Processing with Applications, ISPA 2008. 2008. pp. 669-674 (Proceedings of the 2008 International Symposium on Parallel and Distributed Processing with Applications, ISPA 2008).

@inproceedings{4238179d871f4720bcd77fefede7a317,

title = "Parallelizing optimal multiple sequence alignment by dynamic programming",

abstract = "Optimal multiple sequence alignment by dynamic programming, like many highly dimensional scientific computing problems, has failed to benefit from the improvements in computing performance brought about by multi-processor systems, due to the lack of suitable scheme to manage partitioning and dependencies. A scheme for parallel implementation of the dynamic programming multiple sequence alignment is presented, based on a peer to peer design and a multidimensional array indexing method. This design results in up to 5-fold improvement compared to a previously described master/slave design, and scales favourably with the number of processors used. This study demonstrates an approach for parallelising multi-dimensional dynamic programming and similar algorithms utilizing multi-processor architectures.",

author = "Manal Helal and Hossam El-Gindy and Lenore Mullin and Bruno Gaeta",

year = "2008",

doi = "10.1109/ISPA.2008.93",

language = "English",

isbn = "9780769534718",

series = "Proceedings of the 2008 International Symposium on Parallel and Distributed Processing with Applications, ISPA 2008",

pages = "669--674",

booktitle = "Proceedings of the 2008 International Symposium on Parallel and Distributed Processing with Applications, ISPA 2008",

note = "2008 International Symposium on Parallel and Distributed Processing with Applications, ISPA 2008 ; Conference date: 10-12-2008 Through 12-12-2008",

}

Helal, M, El-Gindy, H, Mullin, L & Gaeta, B 2008, Parallelizing optimal multiple sequence alignment by dynamic programming. in Proceedings of the 2008 International Symposium on Parallel and Distributed Processing with Applications, ISPA 2008., 4725210, Proceedings of the 2008 International Symposium on Parallel and Distributed Processing with Applications, ISPA 2008, pp. 669-674, 2008 International Symposium on Parallel and Distributed Processing with Applications, ISPA 2008, Sydney, NSW, Australia, 10/12/08. https://doi.org/10.1109/ISPA.2008.93

Parallelizing optimal multiple sequence alignment by dynamic programming. / Helal, Manal; El-Gindy, Hossam; Mullin, Lenore et al.
Proceedings of the 2008 International Symposium on Parallel and Distributed Processing with Applications, ISPA 2008. 2008. p. 669-674 4725210 (Proceedings of the 2008 International Symposium on Parallel and Distributed Processing with Applications, ISPA 2008).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Parallelizing optimal multiple sequence alignment by dynamic programming

AU - Helal, Manal

AU - El-Gindy, Hossam

AU - Mullin, Lenore

AU - Gaeta, Bruno

PY - 2008

Y1 - 2008

N2 - Optimal multiple sequence alignment by dynamic programming, like many highly dimensional scientific computing problems, has failed to benefit from the improvements in computing performance brought about by multi-processor systems, due to the lack of suitable scheme to manage partitioning and dependencies. A scheme for parallel implementation of the dynamic programming multiple sequence alignment is presented, based on a peer to peer design and a multidimensional array indexing method. This design results in up to 5-fold improvement compared to a previously described master/slave design, and scales favourably with the number of processors used. This study demonstrates an approach for parallelising multi-dimensional dynamic programming and similar algorithms utilizing multi-processor architectures.

AB - Optimal multiple sequence alignment by dynamic programming, like many highly dimensional scientific computing problems, has failed to benefit from the improvements in computing performance brought about by multi-processor systems, due to the lack of suitable scheme to manage partitioning and dependencies. A scheme for parallel implementation of the dynamic programming multiple sequence alignment is presented, based on a peer to peer design and a multidimensional array indexing method. This design results in up to 5-fold improvement compared to a previously described master/slave design, and scales favourably with the number of processors used. This study demonstrates an approach for parallelising multi-dimensional dynamic programming and similar algorithms utilizing multi-processor architectures.

UR - http://www.scopus.com/inward/record.url?scp=60649089974&partnerID=8YFLogxK

U2 - 10.1109/ISPA.2008.93

DO - 10.1109/ISPA.2008.93

M3 - Conference contribution

AN - SCOPUS:60649089974

SN - 9780769534718

T3 - Proceedings of the 2008 International Symposium on Parallel and Distributed Processing with Applications, ISPA 2008

SP - 669

EP - 674

BT - Proceedings of the 2008 International Symposium on Parallel and Distributed Processing with Applications, ISPA 2008

T2 - 2008 International Symposium on Parallel and Distributed Processing with Applications, ISPA 2008

Y2 - 10 December 2008 through 12 December 2008

ER -

Helal M, El-Gindy H, Mullin L, Gaeta B. Parallelizing optimal multiple sequence alignment by dynamic programming. In Proceedings of the 2008 International Symposium on Parallel and Distributed Processing with Applications, ISPA 2008. 2008. p. 669-674. 4725210. (Proceedings of the 2008 International Symposium on Parallel and Distributed Processing with Applications, ISPA 2008). doi: 10.1109/ISPA.2008.93

Parallelizing optimal multiple sequence alignment by dynamic programming

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this