Parallel progressive Multiple Sequence Alignment

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

Abstract

Multiple Sequence Alignment is an essential tool in the analysis and comparison of biological sequences. Unfortunately, the complexity of this problem is exponential. Currently feasible methods are, therefore, only approximations. The progressive multiple sequence alignment algorithms are the most widespread among these approximations. Still, the computation speed of typical problems is often not satisfactory. Hence, the well known progressive alignment scheme of ClustalW has been subject to parallelization to further accelerate the computation. In the course of this action a unique scheme to parallelize sequence alignment in particular and dynamic programming in general was discovered, which yields an average of n/2 parallel calculations for problem size n. The scalability of O(n) tasks for problem size n can be even maintained for slower networks.

Original languageEnglish
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Pages473-482
Number of pages10
DOIs
Publication statusPublished - 2005
Event10th International Conference on Computer Aided Systems Theory - EUROCAST 2005 - las Palmas de Gran Canaria, Spain
Duration: 7 Feb 200511 Feb 2005

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3643 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference10th International Conference on Computer Aided Systems Theory - EUROCAST 2005
Country/TerritorySpain
Citylas Palmas de Gran Canaria
Period07.02.200511.02.2005

Fingerprint

Dive into the research topics of 'Parallel progressive Multiple Sequence Alignment'. Together they form a unique fingerprint.

Cite this