首页 | 本学科首页   官方微博 | 高级检索  
   检索      


Locality and gaps in RNA comparison.
Authors:Rolf Backofen  Shihyen Chen  Danny Hermelin  Gad M Landau  Mikhail A Roytberg  Oren Weimann  Kaizhong Zhang
Institution:Institute of Computer Science, Albert-Ludwigs Universit?t Freiburg, Freiburg, Germany.
Abstract:Locality is an important and well-studied notion in comparative analysis of biological sequences. Similarly, taking into account affine gap penalties when calculating biological sequence alignments is a well-accepted technique for obtaining better alignments. When dealing with RNA, one has to take into consideration not only sequential features, but also structural features of the inspected molecule. This makes the computation more challenging, and usually prohibits the comparison only to small RNAs. In this paper we introduce two local metrics for comparing RNAs that extend the Smith-Waterman metric and its normalized version used for string comparison. We also present a global RNA alignment algorithm which handles affine gap penalties. Our global algorithm runs in O(m(2)n(1 + lg n/m)) time, while our local algorithms run in O(m(2)n(1 + lg n/m)) and O(n(2)m) time, respectively, where m
Keywords:
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号