Decomposed dynamic programming for concurrent sequence alignment

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.