Enumerating suboptimal alignments of multiple biological sequences efficiently

The multiple sequence alignment problem is very applicable and important in various fields in molecular biology. Because the optimal alignment that maximizes the score is not always biologically most significant, providing many suboptimal alignments as alternatives for the optimal one is very useful. As for the alignment of two sequences, this suboptimal problem is well-studied, but for the alignment of multiple sequences, it has been considered impossible to investigate such suboptimal alignments because of the enormous size of the problem. The optimal multiple alignment can be obtained with A* algorithm, and an efficient algorithm for the k shortest paths problem on general graphs is discovered recently. We extend these algorithms for computation of set of all aligned groups of residues in optimal and suboptimal alignments, and for enumeration of suboptimal alignments. The suboptimal alignments are numerous. Thus we discuss what kind of suboptimal alignment is unnecessary to enumerate, and propose an efficient technique to enumerate only necessary alignments. The practicality of these algorithms are demonstrated through experiments. Moreover, the property of suboptimal alignments of multiple sequences are also examined through experiments.