CBMS-2024B-12

题目来源：Question 12 日期：2024-08-04 题目主题: CS-算法-动态规划

解题思路

这道题目是关于纳米孔测序的信号处理问题，涉及到动态规划和最优化算法。我们需要找到参考信号在测序输出中的最佳匹配位置，同时考虑到时间轴的偏移。主要的难点在于如何高效地处理大量的数据点，以及如何处理时间轴偏移的约束条件。我们将从简单情况开始，逐步构建复杂的动态规划算法来解决这个问题。

Solution

1. Finding $p_1$ for $m=1$

When $m=1$, the problem reduces to finding a single time point $p_1$ such that the dissimilarity ${\sum }_{t=1}^1(B_t-A_{p_t}{)}^2$ is minimized. The algorithm can be described as follows:

1. Initialize $p_1$ to 1.
2. For each $i=1,2,\dots ,n$, compute the dissimilarity $d_i=(B_1-A_i{)}^2$.
3. Find the index $i$ that minimizes $d_i$.

The resulting $p_1$ will be the index that minimizes the dissimilarity.

Algorithm

Input: A sequence {A_t}, reference value B_1
Output: Index p_1 that minimizes dissimilarity
 
1. Initialize min_dissimilarity = infinity
2. Initialize p_1 = 1
3. For i = 1 to n do
     d_i = (B_1 - A_i)^2
     If d_i < min_dissimilarity then
         min_dissimilarity = d_i
         p_1 = i
4. Return p_1

2. Finding $p_1,p_2$ for $m=2$

When $m=2$, the problem involves finding two indices $p_1$ and $p_2$ such that $1\le p_1\le p_2\le n$ and $p_{t+1}-p_t\le W$. The goal is to minimize the dissimilarity ${\sum }_{t=1}^2(B_t-A_{p_t}{)}^2$. The algorithm can be described as follows:

1. Initialize minimum dissimilarity to infinity and $p_1,p_2$ to 1.
2. For each $i=1,2,\dots ,n$, do:
   • For each $j=i,i+1,\dots ,\min (i+W,n)$, do:
     • Compute the dissimilarity $d_{i,j}=(B_1-A_i{)}^2+(B_2-A_j{)}^2$.
     • If $d_{i,j}<\text{min\_dissimilarity}$, update $p_1=i$, $p_2=j$, and $\text{min\_dissimilarity}=d_{i,j}$.

Algorithm

Input: A sequence {A_t}, reference values {B_1, B_2}, window W
Output: Indices p_1, p_2 that minimize dissimilarity
 
1. Initialize min_dissimilarity = infinity
2. Initialize p_1, p_2 = 1
3. For i = 1 to n do
     For j = i to min(i + W, n) do
         d_ij = (B_1 - A_i)^2 + (B_2 - A_j)^2
         If d_ij < min_dissimilarity then
             min_dissimilarity = d_ij
             p_1 = i
             p_2 = j
4. Return p_1, p_2

3. Physical Meaning of $W$

The parameter $W$ represents the maximum allowable fluctuation in the time axis when matching the reference signal to the nanopore sequencer output. It accounts for variations in the speed at which the DNA is read, allowing for some flexibility in aligning the sequences.

4. Recursive Formula for $D_{i,j}$

The minimum dissimilarity $D_{i,j}$ can be computed using the following recurrence relation:

$$D_{i,j}=\underset{x<i,y\le j}{\min }\{D_{x,y}+(B_i-A_j{)}^2\}\text{subject to }j-y\le W=\underset{\max (1,j-W)\le k<j}{\min }{D}_{i-1,k}+(B_i-A_j{)}^2$$

5. Algorithm for Minimum Dissimilarity for $m>2$

To calculate the minimum dissimilarity between the sequence $\{A_t\}$ and the reference signal $\{B_t\}$, we use a dynamic programming approach.

1. Initialize a 2D array $D$ of size $m\times n$ with infinity, where $D_{i,j}$ represents the minimum dissimilarity for the first $i$ elements of the reference sequence mapped to the first $j$ elements of the output sequence.
2. Set $D_{1,j}=(B_1-A_j{)}^2$ for all $j=1,2,\dots ,n$.
3. For each $i=2,3,\dots ,m$, do:
   • For each $j=1,2,\dots ,n$, do:
     • Set $D_{i,j}={\min }_{x=\max (1,j-W)}^{j-1}\{D_{i-1,x}+(B_i-A_j{)}^2\}$.

Time Complexity

The time complexity of this algorithm is $O(m\cdot n\cdot W)$, where:

• $m$ is the length of the reference signal,
• $n$ is the length of the sequence $\{A_t\}$,
• $W$ is the maximum allowed shift between adjacent points.

知识点

动态规划复杂度分析序列比对

难点思路

本题的主要难点在于第 4 和第 5 问，需要正确地推导出动态规划的递推关系，并设计出高效的算法。关键是要理解如何处理时间轴偏移的约束条件，以及如何在保证正确性的同时优化算法的时间复杂度。

解题技巧

对于序列对齐问题，动态规划是一种有效的解决方案。特别是在处理时间序列中的波动和对齐问题时，可以灵活调整对齐窗口 $W$ 来达到最优匹配。

重点词汇

• Dissimilarity: 相异度
• Reference Signal: 参考信号
• Window: 窗口

参考资料

1. Dynamic Time Warping Algorithm: Introduction to the dynamic time warping algorithm, Wikipedia.
2. Time Series Analysis and Its Applications, Third Edition, Robert H. Shumway and David S. Stoffer.