Multiple Sequence Alignment Containing a Sequence of Regular Expressions
Multiple Sequence Alignment Containing a Sequence of Regular Expressions
复制标题
包含正则表达式序列的多序列比对
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
Abdullah N. Arslan
中科院分区：
文献类型：
--
作者：
Abdullah N. Arslan
成对序列比对的经典算法是使用动态规划的Smith Waterman算法。该算法计算使用插入、缺失和取代的比对的最大得分，而不考虑比对的组成。然而，生物学家倾向于将他们关于共同结构或功能的知识应用到比对过程中。对于蛋白质序列的比对，已经提出了几种方法来考虑PROSITE数据库中的基序（一种受限的正则表达式）来指导比对。一种方法修改Smith Waterman动态编程解决方案以奖励包含匹配基序的比对。另一种方法引入了正则表达式约束的序列比对问题，其中成对比对被约束为包含给定的正则表达式。后一种方法从给定的正则表达式构造一个加权有限自动机，并提出了一个动态编程解决方案，该解决方案模拟该自动机的副本，以寻求包含正则表达式的最大分数的对齐。我们概括了这种方法：1）介绍了多序列问题的一种变形，即正则表达式约束下的多序列比对问题，并给出了相应的算法; 2）针对多序列比对问题中要求比对序列包含给定的正则表达式序列的情况，给出了相应的算法。
A classical algorithm for the pairwise sequence alignment is the Smith Waterman algorithm which uses dynamic programming. The algorithm computes the maximum score of alignments that use insertions, deletions, and substitutions, with no consideration given in composition of the alignments. However, biologists favor applying their knowledge about common structures or functions into the alignment process. For alignment of protein sequences, several methods have been suggested for taking into account the motifs (a restricted regular expression) from the PROSITE database to guide alignments. One method modifies the Smith Waterman dynamic programming solution to reward alignments that contain matching motifs. Another method introduces the regular expression constrained sequence alignment problem in which pairwise alignments are constrained to contain a given regular expression. This latter method constructs a weighted finite automaton from a given regular expression, and presents a dynamic programming solution that simulates copies of this automaton in seeking an alignment with maximum score containing the regular expression. We generalize this approach: 1) We introduce a variation of the problem for multiple sequences, namely the regular expression constrained multiple sequence alignment, and present an algorithm for it; 2) We develop an algorithm for the case of the problem when the alignments sought are required to contain a given sequence of regular expressions.