Local multiple sequence alignment using dead-end elimination

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Local multiple sequence alignment is crucial for identifying conserved functional regions in protein families.
• Existing methods for rigorous local multiple alignment can be computationally intensive, limiting their application.

Purpose of the Study:

• To develop an efficient, polynomial-time algorithm for solving the local multiple alignment problem.
• To provide a computationally feasible method for finding globally optimal local alignments of protein sequences.

Main Methods:

• The algorithm employs a dead-end elimination procedure to avoid exhaustive search.
• Rejection criteria are derived within the sum-of-pairs scoring system to eliminate inconsistent segments.
• Iterative application of criteria reduces combinatorial possibilities, leading to convergence.

Main Results:

• The algorithm achieves computational feasibility, with complexity growing polynomially (quadratically and cubically) with sequence length.
• It rapidly reduces search space by eliminating segments provably inconsistent with the optimal alignment.
• The method converges to a unique globally optimal solution in most cases, validated on known protein families.

Conclusions:

• The presented algorithm offers a computationally efficient and rigorous solution for local multiple sequence alignment.
• This advancement facilitates the analysis of protein families and the identification of functionally important regions.