Gorodkin J, Lyngso R B, Stormo G D
Bioinformatics Research Center and Department of Genetics and Ecology, University of Aarhus, Building 540, Ny Munkegade, DK-8000 Aarhus, Denmark.
Genome Inform. 2001;12:184-93.
When a set of coregulated genes share a common structural RNA motif, e.g. a hairpin, most motif search approaches fail to locate the covarying but structurally conserved motif. There do exist methods that can locate structural RNA motifs, like FOLDALIGN, but the main problem with these methods is that they are computationally expensive. In FOLDALIGN, a major contribution to this is the use of a greedy algorithm to construct the multiple alignment. To ensure good quality many redundant computations must be made. However, by applying the greedy algorithm on a carefully selected subset of sequences, near full greedy quality can be obtained. The basic idea is to estimate the order in which the sequences entered a good greedy alignment. If such a ranking, found from all pairwise alignments, is in good agreement with the order of appearance in the multiple alignment, the core structural motif can be found by performing the greedy algorithm on just the top sequences in the ranking. The ranking used in this mini-greedy algorithm is found by using two complementing approaches: 1) When interpreting the FOLDALIGN score as an inner product (kernel), the sequences can be ranked according to their distance to their center of mass; 2) We construct an algorithm that attempts to find the K closest sequences in the vector space associated with the inner product, and the remaining sequences can be ranked by their minimum distance to any of the sequences, or to the center of mass in this set. The two approaches arecompared and merged, and the results discussed. We also show that structural alignments of near full greedy quality can found in significantly reduced time, using these methods. The algorithm is being included in the SLASH (Stem-Loop Align SearcH) server available at http://www.bioinf.au.dk/slash.
当一组共调控基因共享一个共同的结构RNA基序（例如发夹结构）时，大多数基序搜索方法都无法定位到协同变化但结构保守的基序。确实存在一些能够定位结构RNA基序的方法，比如FOLDALIGN，但这些方法的主要问题在于计算成本高昂。在FOLDALIGN中，造成这种情况的一个主要因素是使用了贪婪算法来构建多重比对。为了确保高质量，必须进行许多冗余计算。然而，通过在精心挑选的序列子集上应用贪婪算法，可以获得接近完全贪婪算法的质量。基本思路是估计序列进入良好贪婪比对的顺序。如果从所有两两比对中找到的这种排序与多重比对中的出现顺序高度一致，那么通过仅对排序中靠前的序列执行贪婪算法，就可以找到核心结构基序。这种迷你贪婪算法中使用的排序是通过两种互补方法找到的：1）当将FOLDALIGN分数解释为内积（核）时，可以根据序列到其质心的距离对序列进行排序；2）我们构建了一种算法，试图在与内积相关的向量空间中找到K个最接近的序列，其余序列可以根据它们到这些序列中任何一个的最小距离，或者到该集合质心的最小距离进行排序。对这两种方法进行了比较和合并，并讨论了结果。我们还表明，使用这些方法可以在显著减少的时间内找到接近完全贪婪算法质量的结构比对。该算法已被纳入可在http://www.bioinf.au.dk/slash获取的SLASH（茎环比对搜索）服务器中。
