Levenshtein距离I悬垂基座

2024-03-29 08:17:51 发布

您现在位置:Python中文网/ 问答频道 /正文

我想要一个算法报告这两个序列之间的编辑距离是2:

GCGGCTCCTCTGGGGCGTTCCC公司

GCGGCTCCTCTGGGGCGTTC公司

通过插入2个字符,可以将第一个字符转换为第二个字符,如下所示:

GCGGCTCCTCTGGGGCGTTCCC公司

GCGGCTCCTCTGGGGCGTTC公司

原来两根弦的长度是22。这两个字符串中的前22个字符现在是相同的。这两个字符串之间的levenshtein距离是4,我想用一种方法报告这两个字符串的编辑距离是2。你知道吗

有没有一种方法可以通过python包Levenshtein\u distance函数或我已经在使用的Levenshtein python包来实现这一点?你知道吗

更多详细信息:

我把这个应用到下一代测序数据中。我想比较从每个序列读取的一部分生成的两个序列。序列从全长测序读取开始获得,并且每个测序读取应该是唯一的序列。你知道吗

示例:
读A:ATCGAACCGGTT 读B:atgaacggtt

其中字符串的前四个基将用作每次读取的唯一标识符。序列ATCG是读取A的唯一标识符,ATGA是读取B的唯一标识符。两个读取都包含相同的序列“AACCGGTT”。在比较唯一标识符(ATCG和ATGA)时,我想要一个度量,它返回两个序列之间1的编辑距离。你知道吗

读取唯一标识符:ATCG 插入后读取B唯一id:AT\u GA

我认为字符串右侧(序列末尾)的悬垂基不应受到惩罚,而应在序列左侧受到惩罚的原因如下:

  1. 第一个也是最重要的原因是,仅仅因为字符串的右侧(也就是序列的末尾)有悬垂字符,并不意味着字符在两个被比较的序列之间没有对齐。这只意味着我们没有其他序列中的对应字符来进行比较。对于字符串的左侧,情况并非如此。你知道吗
  2. 通常,字符串左侧的字符(也就是序列读取的开始)比右侧的字符更容易识别(具有更高的质量分数)。你知道吗

Tags: 方法字符串编辑距离报告公司序列标识符
1条回答
网友
1楼 · 发布于 2024-03-29 08:17:51

尽管编写自定义函数来计算“距离”并不困难,但您可以先尝试edlib。因为这是一个非常有效的工具来做这项工作。你知道吗

输入读取A:

ATCGAACCGGTT

输入读取B:

ATGAACCGGTTATG

对齐后:

ATCGAACCGGTT -   # these tailing gap will be ignored
AT-GAACCGGTTATG   # the internal gap is meaningful

您的问题中有python标记,所以我发布了一个使用edlib python包装器的解决方案。

>>> import edlib
>>> edlib.align("ATCGAACCGGTT","ATGAACCGGTTATG", mode="SHW")['editDistance']
1 

SHW mode: gap at query end is not penalized

相关问题 更多 >