A Parallel Algorithm for Three-Profile Alignment Method

Profile-profile alignment is an important technique in the computational biology filed. Several profile-profile alignment methods have been proposed to improve the sensitivity and the alignment quality compared with other sequence-sequence and profile-sequence methods. An increasing number of studies indicated that the three-way alignment may provide additional information or more accurate alignment result than the pair-wise alignment does. Therefore, we propose the dynamic programming based three-profile alignment method, TPA, at first to align three profiles simultaneously. The time and space complexities of TPA are O(n³) and O(n²), respectively. To reduce the complexities of TPA, we further develop the parallel version of TPA, PTPA, which achieves O(n³/p) time and O(n²/p) space complexities, where p is the number of the processor. In the case study I, the result presented that PTPA can find more conserve candidates than those by the profile-profile alignment method (CLUSTALW). In the case study II, we applied the PTPA to the feature amplified voting algorithm (FAVA) to analysis the Amidohydrolase superfamily. Several amino acid residues those were known to be related to the function or the structure of mammalian imidase are identified by PTPA-FAVA.