s****l
发帖数: 10462 | 1 请教一个算法问题
有一个文件A有很多行，每行都是一个20个字母的单词，比如说
1, abbbcdefggabcdeabcde
2, abbbcdefggabcdeabcxy
3, abbbcdefggabcdeabcxz
......
有一个文件B有很多行，每行都是一个20个字母的单词；
1, abhhcdefggabcdeabcde
2, abbxcdefggabcdeabcxz
3, abbpcdefggabcdeabcxz
4, abhhcdefggabcdeabcde
5, abcxcdefggabcdeabcxy
......
对于B文件中每一个单词我要找出在文件A中和它一样，相差一个或者两个字母的单词。
比如B1和A1相差两个字母，满足条件。B2和A2相差一个字母，满足；B2和A3相差一个字
母，也满足，等等。
什么方法比较起来比较快？
谢谢！ | k****f
发帖数: 3794 | 2 google:
suffix tree + string edit distance.
【在 s****l 的大作中提到】
: 请教一个算法问题
: 有一个文件A有很多行，每行都是一个20个字母的单词，比如说
: 1, abbbcdefggabcdeabcde
: 2, abbbcdefggabcdeabcxy
: 3, abbbcdefggabcdeabcxz
: ......
: 有一个文件B有很多行，每行都是一个20个字母的单词；
: 1, abhhcdefggabcdeabcde
: 2, abbxcdefggabcdeabcxz
: 3, abbpcdefggabcdeabcxz
| s****l
发帖数: 10462 | 3 thanks.
This looks like what BLAST does (with dynamic programming), however, it's
not what I really want since my case has only substitutions, but no deletion
or insertion.
【在 k****f 的大作中提到】
: google:
: suffix tree + string edit distance.
| d*z
发帖数: 150 | 4
如果仅仅找出所有相等或最多两个位置不同的串，可以有比较好的Trick.可以将每个串
分成3段（比如6+7+7),然后关于每一段建立索引。
如果两个串之间符合要求，那么必然有一段完全相等。我们可以根据这个将大部分数据
过滤掉
【在 s****l 的大作中提到】
: 请教一个算法问题
: 有一个文件A有很多行，每行都是一个20个字母的单词，比如说
: 1, abbbcdefggabcdeabcde
: 2, abbbcdefggabcdeabcxy
: 3, abbbcdefggabcdeabcxz
: ......
: 有一个文件B有很多行，每行都是一个20个字母的单词；
: 1, abhhcdefggabcdeabcde
: 2, abbxcdefggabcdeabcxz
: 3, abbpcdefggabcdeabcxz
| n******t
发帖数: 4406 | 5 Then just assign deletion and insertion an -infty penalty.
deletion
【在 s****l 的大作中提到】
: thanks.
: This looks like what BLAST does (with dynamic programming), however, it's
: not what I really want since my case has only substitutions, but no deletion
: or insertion.
| w****i
发帖数: 964 | 6 I agree with duz, use partial seeding HASH table is probably the fastest way.
Most short sequence aligners are using this method. It's more efficient
than suffix tree algorithm IMO. | s****l
发帖数: 10462 | 7 Good idea. I think it'll work.
Thanks!
【在 d*z 的大作中提到】
:
: 如果仅仅找出所有相等或最多两个位置不同的串，可以有比较好的Trick.可以将每个串
: 分成3段（比如6+7+7),然后关于每一段建立索引。
: 如果两个串之间符合要求，那么必然有一段完全相等。我们可以根据这个将大部分数据
: 过滤掉
|
|
