کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
393054 | 665564 | 2013 | 18 صفحه PDF | دانلود رایگان |
We provide simple generalizations of the classical Needleman–Wunsch algorithm for aligning two sequences. First, we let both sequences be defined over arbitrary, potentially different alphabets. Secondly, we consider similarity functions between elements of both sequences with ranges in a semiring. Thirdly, instead of considering only ‘match’, ‘mismatch’ and ‘skip’ operations, we allow arbitrary non-negative alignment ‘steps’ S. Next, we present novel combinatorial formulas for the number of monotone alignments between two sequences for selected steps S. Finally, we illustrate sample applications in natural language processing that require larger steps than available in the original Needleman–Wunsch sequence alignment procedure such that our generalizations can be fruitfully adopted.
Journal: Information Sciences - Volume 237, 10 July 2013, Pages 287–304