.png){kind=icon}
返回
An Efficient Alignment Algorithm for Searching Simple Pseudoknots over Long Genomic Sequence
.png){kind=icon}
PRE
AI
DOI：10.1109/TCBB.2012.104.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Structural alignment has been shown to be an effective computational method to identify structural noncoding RNA (ncRNA) candidates as ncRNAs are known to be conserved in secondary structures. However, the complexity of the structural alignment algorithms becomes higher when the structure has pseudoknots. Even for the simplest type of pseudoknots (simple pseudoknots), the fastest algorithm runs in O(mn(3)) time, where m, n are the length of the query ncRNA (with known structure) and the length of the target sequence (with unknown structure), respectively. In practice, we are usually given a long DNA sequence and we try to locate regions in the sequence for possible candidates of a particular ncRNA. Thus, we need to run the structural alignment algorithm on every possible region in the long sequence. For example, finding candidates for a known ncRNA of length 100 on a sequence of length 50,000, it takes more than one day. In this paper, we provide an efficient algorithm to solve the problem for simple pseudoknots and it is shown to be 10 times faster. The speedup stems from an effective pruning strategy consisting of the computation of a lower bound score for the optimal alignment and an estimation of the maximum score that a candidate can achieve to decide whether to prune the current candidate or not.
Keyword:
Noncoding RNAs
pseudoknot
structural alignment
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
I
IF:
3.4
论文数:
3.3K
被引数:
6.4K
机构
引用论文
Structural RNA has lower folding energy than random RNA of the same dinucleotide frequency结构RNA具有比相同二核苷酸频率的随机RNA更低的折叠能量.png)
RNA
OAAI
RNAIF5
OAAI分享收藏
分享收藏
查看更多内容