title: Classification and assessment tools for structural motif discovery algorithms.
abstract: BACKGROUND
  Motif discovery is the problem of finding recurring patterns in biological data. Patterns can be sequential, mainly when discovered in DNA sequences. They can also be structural (e.g. when discovering RNA motifs). Finding common structural patterns helps to gain a better understanding of the mechanism of action (e.g. post-transcriptional regulation). Unlike DNA motifs, which are sequentially conserved, RNA motifs exhibit conservation in structure, which may be common even if the sequences are different. Over the past few years, hundreds of algorithms have been developed to solve the sequential motif discovery problem, while less work has been done for the structural case.
  
  
  METHODS
  In this paper, we survey, classify, and compare different algorithms that solve the structural motif discovery problem, where the underlying sequences may be different. We highlight their strengths and weaknesses. We start by proposing a benchmark dataset and a measurement tool that can be used to evaluate different motif discovery approaches. Then, we proceed by proposing our experimental setup. Finally, results are obtained using the proposed benchmark to compare available tools. To the best of our knowledge, this is the first attempt to compare tools solely designed for structural motif discovery.
  
  
  RESULTS
  Results show that the accuracy of discovered motifs is relatively low. The results also suggest a complementary behavior among tools where some tools perform well on simple structures, while other tools are better for complex structures.
  
  
  CONCLUSIONS
  We have classified and evaluated the performance of available structural motif discovery tools. In addition, we have proposed a benchmark dataset with tools that can be used to evaluate newly developed tools.
authors.affiliation: King Saud University, College of Computer and Information Sciences, Riyadh, Kingdom of Saudi Arabia. badrghada@hotmail.com
authors.forename: Ghada
authors.initials: G
authors.lastname: Badr
authors.forename: Isra
authors.initials: I
authors.lastname: Al-Turaiki
authors.forename: Hassan
authors.initials: H
authors.lastname: Mathkour
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D017124:Conserved Sequence; D015233:Models, Statistical; D059372:Nucleotide Motifs; D017423:Sequence Analysis, RNA / Q000379:methods*
references.citation: Curr Opin Struct Biol. 2006 Jun;16(3):270-8
references.pmid: 16713706
references.citation: Bioinformatics. 2006 Oct 15;22(20):2480-7
references.pmid: 16908501
references.citation: Nucleic Acids Res. 1997 Sep 15;25(18):3724-32
references.pmid: 9278497
references.citation: Bioinformatics. 2004 Jul 10;20(10):1591-602
references.pmid: 14962926
references.citation: J Comput Biol. 2006 Mar;13(2):267-82
references.pmid: 16597239
references.citation: J Mol Biol. 1999 May 21;288(5):911-40
references.pmid: 10329189
references.citation: Bioinformatics. 2005 May 1;21(9):1815-24
references.pmid: 15657094
references.citation: Nucleic Acids Res. 2010 Jan;38(Database issue):D280-2
references.pmid: 19880381
references.citation: Nucleic Acids Res. 2000 Feb 15;28(4):991-9
references.pmid: 10648793
references.citation: Nucleic Acids Res. 2004 Jun 15;32(10):3258-69
references.pmid: 15199174
references.citation: Proc Natl Acad Sci U S A. 1980 Nov;77(11):6309-13
references.pmid: 6161375
references.citation: Nucleic Acids Res. 2005 Jul 1;33(Web Server issue):W650-3
references.pmid: 15980555
references.citation: IEEE/ACM Trans Comput Biol Bioinform. 2006 Apr-Jun;3(2):126-40
references.pmid: 17048399
references.citation: Biopolymers. 1990 May-Jun;29(6-7):1105-19
references.pmid: 1695107
references.citation: Mol Biotechnol. 2009 Feb;41(2):180-93
references.pmid: 18979204
references.citation: Nucleic Acids Res. 1994 Jun 11;22(11):2079-88
references.pmid: 8029015
references.citation: Bioinformatics. 2006 Feb 15;22(4):445-52
references.pmid: 16357030
references.citation: Phys Rev E Stat Nonlin Soft Matter Phys. 2005 Feb;71(2 Pt 1):021913
references.pmid: 15783358
references.citation: BMC Bioinformatics. 2006 May 05;7:244
references.pmid: 16677380
references.citation: IEEE/ACM Trans Comput Biol Bioinform. 2007 Oct-Dec;4(4):596-610
references.pmid: 17975271
references.citation: Nucleic Acids Res. 2001 May 15;29(10):2135-44
references.pmid: 11353083
references.citation: PLoS Comput Biol. 2007 Oct;3(10):1896-908
references.pmid: 17937495
references.citation: J Mol Biol. 1999 Feb 5;285(5):2053-68
references.pmid: 9925784
references.citation: Biopolymers. 1999 Feb;49(2):145-65
references.pmid: 10070264
references.citation: Nucleic Acids Res. 2005 Jan 1;33(Database issue):D121-4
references.pmid: 15608160
references.citation: Nucleic Acids Res. 2002 Sep 1;30(17):3886-93
references.pmid: 12202774