On Using Consistency Consistently in Multiple Sequence Alignments

Multiple Sequence Alignment (MSA) is a fundamental step for the resolution of a variety of problems in Computational Biology. Given its computational complexity, typically one of a variety of heuristic-based strategies, proposed and revised over the last two or more decades, is adopted to produce a solution, although, with no guarantee of optimality. Traditionally, existing heuristics are classified into one of four distinct approaches, with scientists generally choosing a recent heuristic from the approach they believe to be the best. This might mean however that some older but sound heuristics are being ignored because they have not been modernized to use more recent techniques. Using a framework being developed to unify algorithm development for MSA by integrating the four classes, initial work presented in this paper combines existing techniques from different classes to effectively create improved heuristics. The feasibility of this idea is endorsed by a detailed analysis of novel variants of existing non-consistency-based strategies that have incorporated consistency and their comparison with current state-of-the-art consistency-based heuristics. Results using the BAliBase benchmark show that the use of consistency has a huge impact on accuracy, especially for sequences with low identity. More importantly, the new variants produce better accuracies than the most commonly used consistency-based MSA tools.