Performance assessment of protein multiple sequence alignment algorithms based on permutation similarity measurement

Area of Science:

• Bioinformatics
• Computational Biology
• Evolutionary Biology

Background:

• Protein multiple sequence alignment is crucial for analyzing biological evolution and predicting protein structures.
• Existing alignment algorithms have limitations and inherent deficiencies.
• Robust evaluation methods are needed to compare these algorithms effectively.

Purpose of the Study:

• To propose and validate a novel method, permutation similarity, for evaluating protein multiple sequence alignment algorithms.
• To assess the performance of widely used algorithms including Dialign, Tcoffee, ClustalW, and Muscle.
• To compare the effectiveness of these algorithms based on evolutionary distance order.

Main Methods:

• Developed the permutation similarity metric to assess alignment algorithms.
• Utilized the longest common subsequence (LCS) method to define similarity between permutations.
• Applied permutation similarity to evaluate Dialign, Tcoffee, ClustalW, and Muscle.

Main Results:

• Permutation similarity provides robust evaluations by focusing on the relative order of evolutionary distances.
• The method successfully differentiated the performance of the assessed algorithms.
• Comparisons revealed varying strengths and weaknesses among Dialign, Tcoffee, ClustalW, and Muscle.

Conclusions:

• Permutation similarity is a valuable tool for evaluating protein multiple sequence alignment algorithms.
• The study offers insights into the comparative performance of leading alignment tools.
• This approach enhances the understanding of algorithm deficiencies and aids in selecting appropriate methods.