title: Structator: fast index-based search for RNA sequence-structure patterns.
abstract: BACKGROUND
  The secondary structure of RNA molecules is intimately related to their function and often more conserved than the sequence. Hence, the important task of searching databases for RNAs requires to match sequence-structure patterns. Unfortunately, current tools for this task have, in the best case, a running time that is only linear in the size of sequence databases. Furthermore, established index data structures for fast sequence matching, like suffix trees or arrays, cannot benefit from the complementarity constraints introduced by the secondary structure of RNAs.
  
  
  RESULTS
  We present a novel method and readily applicable software for time efficient matching of RNA sequence-structure patterns in sequence databases. Our approach is based on affix arrays, a recently introduced index data structure, preprocessed from the target database. Affix arrays support bidirectional pattern search, which is required for efficiently handling the structural constraints of the pattern. Structural patterns like stem-loops can be matched inside out, such that the loop region is matched first and then the pairing bases on the boundaries are matched consecutively. This allows to exploit base pairing information for search space reduction and leads to an expected running time that is sublinear in the size of the sequence database. The incorporation of a new chaining approach in the search of RNA sequence-structure patterns enables the description of molecules folding into complex secondary structures with multiple ordered patterns. The chaining approach removes spurious matches from the set of intermediate results, in particular of patterns with little specificity. In benchmark experiments on the Rfam database, our method runs up to two orders of magnitude faster than previous methods.
  
  
  CONCLUSIONS
  The presented method's sublinear expected running time makes it well suited for RNA sequence-structure pattern matching in large sequence databases. RNA molecules containing several stem-loop substructures can be described by multiple sequence-structure patterns and their matches are efficiently handled by a novel chaining method. Beyond our algorithmic contributions, we provide with Structator a complete and robust open-source software solution for index-based search of RNA sequence-structure patterns. The Structator software is available at http://www.zbh.uni-hamburg.de/Structator.
authors: Center for Bioinformatics, University of Hamburg, Bundesstrasse 43, 20146 Hamburg, Germany.
authors: Fernando
authors: F
authors: Meyer
authors: Stefan
authors: S
authors: Kurtz
authors: Rolf
authors: R
authors: Backofen
authors: Sebastian
authors: S
authors: Will
authors: Michael
authors: M
authors: Beckstette
references: Bioinformatics. 2007 Apr 15;23(8):926-32
references: 17324941
references: Trends Genet. 1997 Dec;13(12):497-8
references: 9433140
references: Nucleic Acids Res. 2005 Apr 28;33(8):2433-9
references: 15860779
references: Nucleic Acids Res. 1997 Sep 15;25(18):3724-32
references: 9278497
references: BMC Bioinformatics. 2010 Apr 30;11:222
references: 20433706
references: Bioinformatics. 2005 May 1;21(9):1815-24
references: 15657094
references: Nucleic Acids Res. 2008 May;36(9):e52
references: 18420654
references: Bioinformatics. 2003;19 Suppl 1:i232-40
references: 12855464
references: Nucleic Acids Res. 2003 Jul 1;31(13):3608-12
references: 12824377
references: EMBO J. 1998 Oct 15;17(20):6069-75
references: 9774350
references: Nucleic Acids Res. 2011 Jan;39(Database issue):D141-5
references: 21062808
references: Bioinformatics. 2009 Dec 15;25(24):3251-8
references: 19828575
references: BMC Bioinformatics. 2004 Sep 30;5:140
references: 15458580
references: PLoS Comput Biol. 2007 Mar 30;3(3):e56
references: 17397253
references: BMC Bioinformatics. 2007 Apr 19;8:130
references: 17445273
references: J Mol Biol. 2002 Mar 22;317(2):191-203
references: 11902836
references: Comput Appl Biosci. 1990 Oct;6(4):325-31
references: 1701686
references: Nucleic Acids Res. 2006 Jul 1;34(Web Server issue):W423-8
references: 16845040
references: Nucleic Acids Res. 2001 Nov 15;29(22):4724-35
references: 11713323
references: Methods Mol Biol. 2007;395:527-44
references: 17993696
references: J Mol Biol. 2001 Nov 9;313(5):1003-11
references: 11700055
references: Bioinformatics. 2005 Aug 15;21(16):3352-9
references: 15972285
references: PLoS Comput Biol. 2007 Apr 13;3(4):e65
references: 17432929
references: Bioinformatics. 2009 Aug 1;25(15):1974-5
references: 19398448
references: Trends Genet. 2010 Jan;26(1):21-8
references: 19944475
references: Bioinformatics. 2005 Sep 1;21(17):3516-23
references: 16020472
references: IEEE/ACM Trans Comput Biol Bioinform. 2004 Jan-Mar;1(1):53-62
references: 17048408
references: Nat Rev Genet. 2004 Apr;5(4):316-23
references: 15131654
references: Nature. 2006 Sep 14;443(7108):167-72
references: 16915236
references: BMC Bioinformatics. 2006 Aug 24;7:389
references: 16930469
references: Bioinformatics. 2009 May 15;25(10):1335-7
references: 19307242
references: Nucleic Acids Res. 2009 Jan;37(Database issue):D136-40
references: 18953034
references: BMC Bioinformatics. 2003 Sep 22;4:44
references: 14499004
references: J Mol Biol. 2002 Jun 21;319(5):1059-66
references: 12079347
references: Nucleic Acids Res. 2003 Jul 1;31(13):3423-8
references: 12824339