Decomposed dynamic programming for concurrent sequence alignment

Research output: Chapter in Book/Report/Conference proceedingsConference contributionpeer-review

Abstract

Inference of evolutionary relationships and DNA analysis heavily rely on multiple sequence alignment. Unfortunately, multiple sequence alignments are hard to compute. Usually, only approximations are feasible. Still, these approximations take their time to render. Therefore, the well known progressive alignment algorithm, ClustalW has been subject to further acceleration. This acceleration was mainly achieved through parallelization. A significant part of this algorithm is embarrassingly parallel and trivial to decompose. To achieve a meaningful overall acceleration, however, dynamic programming had to be decomposed too, which is used during most stages. The discovered scheme can probably be used to accelerate other matrix calculations. Simulations show promising results for the discovered technique. Included are additional modifications to adjust it to slow networks. Eventually, progressive multiple sequence alignment proved extremely well parallelizable.

Original languageEnglish
Title of host publicationWMSCI 2005 - The 9th World Multi-Conference on Systemics, Cybernetics and Informatics, Proceedings
Pages104-108
Number of pages5
Publication statusPublished - 2005
Event9th World Multi-Conference on Systemics, Cybernetics and Informatics, WMSCI 2005 - Orlando, FL, United States
Duration: 10 Jul 200513 Jul 2005

Publication series

NameWMSCI 2005 - The 9th World Multi-Conference on Systemics, Cybernetics and Informatics, Proceedings
Volume4

Conference

Conference9th World Multi-Conference on Systemics, Cybernetics and Informatics, WMSCI 2005
CountryUnited States
CityOrlando, FL
Period10.07.200513.07.2005

Keywords

  • Concurrency
  • Decomposition
  • Dynamic programming
  • Sequence alignment

Fingerprint Dive into the research topics of 'Decomposed dynamic programming for concurrent sequence alignment'. Together they form a unique fingerprint.

Cite this