BlockMSA
is a biclustering-based local Multiple Sequence
Alignment (MSA) Program for RNA sequences. Biclustering is a clustering method that
simultaneously clusters both the domain and range of a relation. A challenge in multiple sequence alignment
(MSA) is that the alignment of sequences is often intended to reveal groups of
conserved functional subsequences.
Simultaneously, the grouping of the sequences can impact the alignment;
precisely the kind of dual situation biclustering
algorithms are intended to address. We define a representation of
the MSA problem enabling the application of biclustering
algorithms. We incorporate this method into a divide-and-conquer algorithm for
local MSA, such that groups of similar sequences and alignments on them are
simultaneously identified, and further alignment is accomplished by dividing
the set of sequences and their contents. The net result is both a multiple
sequence alignment and a hierarchical clustering of the sequences.