Accelerating phylogeny-aware alignment with indel evolution using short time Fourier transform.

Area of Science:

• Bioinformatics
• Computational Biology
• Evolutionary Biology

Background:

• Frequentist dynamic programming (DP) for multiple sequence alignment using the Poisson Indel Process (PIP) offers evolutionary meaningful gaps but has cubic time complexity.
• Existing methods can suffer from 'over-alignment' bias, impacting the accuracy of evolutionary inference.

Purpose of the Study:

• To develop an accelerated, phylogeny-aware multiple sequence alignment method.
• To reduce the computational complexity of the PIP-based alignment approach.
• To improve the efficiency of evolutionary indel-based alignment for large datasets.

Main Methods:

• Converted amino acid sequences to physicochemical property sequences.
• Identified homologous blocks using multi-scale short-time Fourier transform.
• Employed sparse three-dimensional DP matrices under PIP, aligning homologous and linking blocks as independent sub-matrices.

Main Results:

• The new method significantly reduces computational complexity compared to the original PIP approach.
• The algorithm leverages parallel computing for substantial theoretical speed-up.
• Demonstrated effectiveness on real biological sequence data.

Conclusions:

• The proposed technique offers a computationally efficient and scalable solution for evolutionary multiple sequence alignment.
• This acceleration is crucial for analyzing large-scale genomic and proteomic datasets.
• The method maintains the evolutionary meaningful gap patterns characteristic of the PIP model.