GR-Aligner: An algorithm for aligning pairwise genomic sequences containing rearrangement events

Motivation: Homologous genomic sequences between species usually contain different rearrangement events. Whether some specific patterns existed in the breakpoint regions that caused such events to occur is still unclear. To resolve this question, it is necessary to determine the location of breakpoints at the nucleotide level. The availability of sequences near breakpoints would further facilitate the related studies. We thus need a tool that can identify breakpoints and align the neighboring sequences. Although local alignment tools can detect rearrangement events, they only report a set of discontinuous alignments, where the detailed alignments in the breakpoint regions are usually missing. Global alignment tools are even less appropriate for these tasks since most of them are designed to align the conserved regions between sequences in a consistent order, i.e. they do not consider rearrangement events. Results: We propose an effective and efficient pairwise sequence alignment algorithm, called GR-Aligner (Genomic Rearrangement Aligner), which can find breakpoints of rearrangement events by integrating the forward and reverse alignments of the breakpoint regions flanked by homologously rearranged sequences. In addition, GR-Aligner also provides an option to view the alignments of sequences extended to the breakpoints. These outputs provide materials for studying possible evolutionary mechanisms and biological functionalities of the rearrangement.