RNAmountAlign: efficient software for local, global, semiglobal pairwise and multiple RNA sequence/structure alignment

• DOI: 10.48550/arxiv.1808.03672
• Publication Date: 2018-01-01
• Authors: Amir H. Bayegan; Peter Clote
• Keywords: Smith–Waterman algorithm; Multiple sequence alignment; Structural alignment; Alignment-free sequence analysis; Sequence (biology)

Alignment of structural RNAs is an important problem with a wide range applications. Since function often determined by molecular structure, RNA alignment programs should take into account both sequence and base-pairing information for homology identi^Lcation. A number successful are heuristic versions Sanko^K's optimal algorithm. Most them require O(n4) run time. This paper describes C++ software, RNAmountAlign, sequence/structure that runs in O(n3) time O(n2) space; moreover, our software returns p-value (transformable to expect value E) based on Karlin-Altschul statistics local alignment, as well parameter ^Ltting global alignment. Using incremental mountain height, representation computable cubic time, RNAmountAlign implements quadratic pairwise local, global/semiglobal (query search) using weighted combination similarity. capable performing progressive multiple well. Benchmarking against LocARNA, LARA, FOLDALIGN, DYNALIGN STRAL shows has reasonably good accuracy much faster supporting all types.