[题型设计]字符串相似度匹配

发表于 更新于 分类于 阅读次数： 本文字数： 497 阅读时长 ≈ 1 分钟

近段时间接触了基因比对算法, 业界最常使用的是BWA算法, 我现在还不了解具体如何实现的, 这里只是准备把算法用计算机的语言描述一下.

请听题:

假设有一长字符串, 有以下特征:

  1. 字符串长度大约为30亿
  2. 所有字符由以下五种组成: ATGCN, 前面为4钟碱基, 最后一个为未知碱基
  3. 该字符串为确定字符串, 即所有位置都已经正确

另外有一短字符串, 短字符串有如下特性:

  1. 长度为100或者150左右的固定长度字符
  2. 字符串也有ATGC组成
  3. 由实验误差原因, 已知该字符串每个位置都可能出现p的概率误差, 称之为测序误差
  4. 由于生物学的缘由, 会出现字符出错, 也有出现字符丢失, 或者字符增加, 这种误差被称之为突变误差

此外, 还有一点:

  1. 短字符串比较多, 可能长字符串同一个位置会有段短字符串匹配, 也可能没一个匹配到的

  2. 短序列的起始和结束位置是不固定,

  3. 目前的高级的测序仪器, 平均所有短序列的覆盖深度为50X, 即总共的字符为30亿*50, 如果短字符长度为100的话, 就有30亿*50/100 = 15亿条.

问题:

  1. 设计一个概念模型来计算字符的相似度, 并说明如何确定匹配阈值, 即达到什么概论, 可以认为没有匹配上.
  2. 设计一个算法能够尽快的计算出所有短序列在长序列之中位置