序列的平滑

Question

我认为应该有一个算法用于此 - 可能在像生物信息学这样的领域(问题提醒我一些序列对齐)所以我希望有人可以帮助我在这里.

问题如下:假设我已经将一些数据分类为两个不同的类X和Y.结果可能如下所示:.. XXX Y XXX ..进一步假设我们对这些类有一些领域知识并且知道连续不到一定数量的实例是极不可能的(即一个序列中不可能有少于4个X或Ys - 最好是每个类可以使用不同的阈值,但这不是必须的).因此,如果我们使用这种领域知识,那么我们希望用X替换中间的单个Y是"显而易见的".

因此,算法应采用一系列分类实例和类的阈值(如果它简化了问题,则为1的阈值),并尝试找到满足属性的序列(没有比给定阈值短的类序列).显然,可能存在极大数量的正确解决方案(例如,在上面的示例中,我们也可以用Y替换所有X),因此我认为合理的优化标准将是最小化替换次数.

我不需要一个特别有效的算法,因为实例的数量会相当小(比如<4k),我们只有两个类.此外,由于这显然只是一种启发式方法,如果它们极大地简化了算法,我可以使用一些不准确的方法.

Answer 1

您可以使用动态编程，如以下伪代码草图所示（为简单起见，此代码假设阈值是连续 3 个 X 或 Y，而不是 4 个）：

min_switch(s):
  n = len(s)
  optx = array(4, n, infinity) // initialize all values to infinity
  opty = array(4, n, infinity) // initialize all values to infinity
  if s[0] == 'X':
    optx[1][0] = 0
    opty[1][0] = 1
  else:
    optx[1][0] = 1
    opty[1][0] = 0
  for i in {1, n - 1}:
    x = s[i]
    if x == 'X':
      optx[1][i] = opty[3][i - 1]
      optx[2][i] = optx[1][i - 1]
      optx[3][i] = min(optx[2][i - 1], optx[3][i - 1])
      opty[1][i] = 1 + min(optx[1][i - 1], optx[2][i - 1], optx[3][i - 1])
      opty[2][i] = 1 + opty[1][i - 1]
      opty[3][i] = 1 + min(opty[2][i - 1], opty[3][i - 1])
    else:
      optx[1][i] = 1 + min(opty[1][i - 1], opty[2][i - 1], opty[3][i - 1])
      optx[2][i] = 1 + opty[1][i - 1]
      optx[3][i] = 1 + min(opty[2][i - 1], opty[3][i - 1])
      opty[1][i] = optx[3][i - 1]
      opty[2][i] = opty[1][i - 1]
      opty[3][i] = min(opty[2][i - 1], opty[3][i - 1])
  return min(optx[3][n - 1], opty[3][n - 1])

上面的代码本质上是计算创建直到第 i 个字符的平滑序列的最低成本，该序列存储一行中所有相关数量的连续 X 或 Y（一行中的 1、2 或 3）的最佳值。更正式一点

• opt[i][0][k]存储将字符串转换s[0...k] 为平滑序列的最小成本，然后以连续的 X 结尾 i。3 次或以上的游程计入 中opt[3][0][k]。
• opt[0][j][k]存储将字符串转换s[0...k] 为平滑序列的最小成本，然后以连续的 Y 结尾 j。3 次或以上的游程计入 中opt[0][3][k]。

将其转换为返回序列以及最优成本的算法很简单。

请注意，上面代码中的某些情况可能是不必要的，它只是从约束导出的简单递归。