碩論：最長共同近乎波動子序列問題 1 ｜The Longest Common Almost Wave Subsequence Problem (LCaWS)

這篇介紹我的碩論：最長共同近乎波動子序列問題 (LCaWS)，波動序列問題如何發展？LCaWS如何應用於即時監測心律異常？如何有效率解決LCaWS問題？未來可以如何改善LCaWS演算法？

文章連結

  1. 碩論：最長共同近乎波動子序列問題 1
    1. 主要貢獻
    2. 摘要
    3. 問題簡介與應用
    4. LCaWS演算法概念
    5. LCaWSt演算法
  2. 碩論：最長共同近乎波動子序列問題 2
    1. LCaWSr演算法
    2. 結論與改善

ㄧ、主要貢獻

（一）定義最長共同近乎波動子序列 (LCaWS)問題

我們定義一個更接近真實情境的新問題——最長共同近乎波動子序列 (the longest common almost wave subsequence, LCaWS)問題，LCaWS可視為最長共同波動子序列 (LCWS)更廣義的問題。由於真實波動序列是存在些微誤差的，例如：真實心電圖 (ECG)的波可能存在一些微小的雜訊，而這些雜訊我們其實可以忽略，因此在此情境中，LCaWS比LCWS更能應用於真實情境中。

（二）給出有效率的演算法去解決LCaWS

LCaWS有兩個子問題，分別為定趨勢之最長共同近乎波動子序列(LCaWSt)問題與最長共同近乎波動子序列但轉折次數小於等於r (LCaWSr)問題。解決LCaWSt 問題的時間複雜度為 O(mnc)；解決LCaWSr問題度時間複雜度為 O(rmnc)，這裡的m和n分別為兩條輸入序列的長度，r為段數，c為公差。

（三）即時監測心律異常的解決方案之一

綜合以上兩點，我們的LCaWSr演算法可應用於即時監測心律異常，概念上我們可以透過比較連續兩個心率周期波的相似度，來即時判斷現在使用者心律是否異常？再加上一個正常的心率周期波是由 P、Q、R、S 和 T 波所組成且開頭為近乎遞增段的合成波，因此這問題其實就是LCaWSr，且我們的演算法可以有效率去算出鄰波間的相似度。


二、摘要

波動序列在生活中很常見，舉凡金融、天氣與醫療，因此Chen與Yang於2020年提出最長波動子序列(LWS)問題，且Chang與Yang於2021年提出最長共同波動子序列(LCWS)問題。然而LWS和LCWS都不允許波動序列有誤差，但現實的波動序列存在些微誤差，故我們一般化LCWS問題成最長共同近乎波動子序列(LCaWS)問題。

LCaWS問題有兩個子問題，分別為LCaWSt問題與LCaWSr問題。給定兩條數字序列A、B、一條趨勢序列T、段數r與公差c，LCaWSt問題要找出A與B的最長共同波動子序列，其趨勢與T的前綴一致，且由近乎遞增與遞減段交替組成；LCaWSr問題則要找出A與B的最長共同波動子序列，其序列最多由r段近乎遞增與遞減段交替組成。最後我們花O(mnc)時間與O(nc)空間解決LCaWSt問題，且花O(rmnc)時間與O(rnc)空間解決LCaWSr問題，其m和n分別為A和B的長度。


三、問題

（ㄧ）發展簡介

最長共同近乎波動子序列問題演變圖

最長遞增子序列 (LIS)問題是要找一條序列中，最長的遞增子序列。由於 LIS 問題無法描述波動序列，但波動序列又很常出現於生活中，如：金融、氣象與醫療。於是 Chen 和 Yang [CY20]在 2020 年定義最長波動子序列(LWS)問題，隔年Chang 和 Yang [CY21]又定義最長共同波動子序列(LCWS)問題。然而 LWS 和 LCWS 都不允許波動序列有誤差，但現實的波動序列存在些微誤差，故我們一般化 LCWS 問題成最長共同近乎波動子序列(LCaWS)問題。

（二）應用

LCaWSt 問題要找出兩條序列 A 與 B 的最長共同波動子序列，其趨勢與給定的趨勢序列 T 前綴一致，且由近乎遞增與遞減段交替組成。LCaWSr 問題則要找出兩條序列 A 與 B 的最長共同波動子序列，其序列最多由 r 段近乎遞增與遞減段交替組成。

(a) 心電圖 (b) 正常心律週期

我們可以使用LCaWSr演算法來及時偵測心電圖中的每個心率周期波是否異常，這可以透過比較連續兩個心率周期波的相似度來判斷是否異常。(b) 顯示一個正常的心率周期波是由P、Q、R、S和T波所組成且開頭為近乎遞增段的合成波。(a) 顯示在正常的心電圖中的連續兩個周期波應要很相似。因此，如果相似度過低，則代表當前心率狀態異常。在此應用中，LCaWSr演算法比最長共同子序列(LCS)演算法更適合，因為我們的目標是一個六段且開頭為近乎遞增段的波動序列。


四、演算法

（一）LCaWS演算法概念

LCaWS演算法的核心就是：

  1. 延伸潛力解
  2. 繼承轉折點的解

因此LCaWSt與LCaWSr演算法都會使用L表去紀錄len和base，同時使用β表去紀錄潛力解，最後只需靠β表即可快速完成延伸工作。然而不一樣的地方是：

  1. L表數量：LCaWSt只需要維護＋與−兩種L表，即維護最後兩段的資料；但LCaWSr需要維護所有段數的資料，即r段的資料。因此在時間複雜度上LCaWSr更花時間，LCaWSt為O(mnc)，而LCaWSr為O(rmnc)。
  2. 轉折點：LCaWSt一開始就有給予趨勢序列T，因此我們透過T就可以知道哪些位置是轉折點，所以只有當長度為轉折點時，才需要做繼承；但LCaWSr只有給段數r，因此任何位置當是潛在的轉折點，所以每次都需要做繼承。

最後LCaWS演算法的虛擬碼、正確性與複雜度的證明，都放在我的碩論中，有興趣者可以自行下載閱讀。

（二）LCaWSt 問題與演算法

LCaWSt 問題要找出兩條序列 A 與 B 的最長共同波動子序列，其趨勢與給定的趨勢序列 T 前綴一致，且由近乎遞增與遞減段交替組成。

LCaWSt問題範例

A = <3, 2, 7, 4, 5, 2, 8>、B = <3, 8, 2, 7, 4, 5, 2>、T = <0, 1, 1, 0, 0, 1, 1>和c = 3，則LCWSt = <2, 4, 5, 2>、LCaWSt = <3, 2, 7, 5, 2>。這裡的紅色實線代表近乎遞增段，藍色虛線代表近乎遞減段。

我們使用L表與β表去解決LCaWSt問題，L表和β表每一格都是記錄2元組<base, len>的集合。

  • L＋(i, j)中每個2元組的len為A1..i和B1..j的LCaWSt長度，其最後一個元素為bj且最後一段為近乎遞增段，而base則為最後一段的最大值。
  • L−(i, j)則是記錄近乎遞減段的長度與最小值。
  • β＋(i, j)會從L＋(i-1, j)中收集未來接上ai會形成近乎遞增段的2元組，同時也會繼承β＋(i, j-1)所有2元組。
  • β−(i, j) 則是收集未來會形成近乎遞減段的2元組。
因此，β表會收集未來有潛力的2元組，為了更好理解LCaWSt演算法，以下使用L表的虛線藍框框代表未來有潛力的2元組（β）。

第一回（a1 = 3）：

  • ＋：我們會得到<3>這個長度為1的答案，因為a1 = b1 = 3。因此L＋(1, 1) = {<3,1>}，這代表3是在最後近乎遞增段的最大值且其長度為1。
  • −：然而<3,1> ∉ L−(1, 1)，因為位置1是近乎遞增段。

第二回（a2 = 2）：

  • ＋：<3, 1> ∈ L＋(1, 1) 是可以接上2的近乎遞增潛力解，因爲我們容許2可以接在3後面，因此L＋(2, 3) = {<2,1>, <3,2>}，其可能解為{<2>, <3-2>}；同時L＋(2, 7)也是如此。

第三回（a3 = 7）：

  • ＋：<3, 2> ∈ L＋(2, 3) 是可以接上7的近乎遞增潛力解，因此L＋(3, 4) = {<7,3>}，其可能解為{<3-2-7>}。
  • −：同時位置3是由上而下的轉折點，所以它可以被視為當前近乎遞增段的結尾以及下一個近乎遞減段的開頭，故L−(3, 4) 可以繼承 <7,3> ∈ L＋(3, 4) ，所以L−(3, 4) = {<7,3>}，其可能解為{<3-2-7>}。

第四回（a4 = 4）：

  • ＋：<3, 2> ∈ L＋(3, 3) 是可以接上4的近乎遞增潛力解，因此L＋(4, 5) = {<4,3>}，其可能解為{<3-2-4>}。注意<7, 3> ∈ L＋(3, 4) 不是近乎遞增潛力解，因為我們不允許4接在7後面。
  • −：<7, 3> ∈ L−(3, 4) 是可以接上4的近乎遞減潛力解，因此L−(4, 5) = {<4,4>}，其可能解為{<3-2-7-4>}。

    第五回（a5 = 5）：

    • ＋：<3, 2> ∈ L＋(4, 3) 是可以接上5的近乎遞增潛力解，因此<5,3> ∈ L＋(5, 5) ，注意<7, 3> ∈ L＋(4, 4) & <4, 3> ∈ L＋(4, 5) 不是近乎遞增潛力解，因為位置4是近乎遞減段。由於位置5是由下而上的轉折點，所以 L＋(5, 5) 可以繼承 <4,5> ∈ L−(5, 5) ，故 L＋(5, 5) = {<5,5>}，其可能解為{<3-2-7-4-5>}，這要注意5才是近乎遞增段，而4是近乎遞減段，所以L＋(5, 5) 紀錄 <5,5> 而非 <4,5>。
    • −：<7, 3> ∈ L−(4, 4) & <4, 4> ∈ L−(4, 5) 是可以接上5的近乎遞減潛力解，因此L−(5, 5) = {<5,4>, <4,5>}，其可能解為{<3-2-7-5>, <3-2-7-4-5>}。

    第六回（a6 = 2）：

    • ＋：<2,1>, <3,2> ∈ L＋(5, 2) 是可以接上2的近乎遞增潛力解，因此<2,2>, <3,3> ∈ L＋(6, 7)。 注意<4,3> ∈ L＋(5, 5) & <5,5> ∈ L＋(5, 6)不是近乎遞增潛力解，前者因為位置4是近乎遞減段，後者因為我們不允許5後面接2 。由於位置5是由下而上的轉折點，所以 L＋(6, 7) 可以繼承 <2,5> ∈ L−(6, 7) ，故<2,5> ∈ L＋(6, 7)，最後L＋(6, 7) = {<2,5>, <3,3>}，其可能解為{<3-2-7-5-2>, <3-2-2>}
    • −：<5, 4> ∈ L−(5, 6) 是可以接上2的近乎遞減潛力解，因此 L−(6, 7) = {<2,5>}，其可能解為{<3-2-7-5-2>}。注意<4,5> ∈ L−(5, 6)不是近乎遞減潛力解，因為位置6是近乎遞增段。

    其餘部分也用相似方式去更新，最後我們會得到長度為5的LCaWSt，因為<2,5>是在L＋(7, j)中有最大的長度。除了長度，我們可以使用L表追溯出LCaWSt為<3-2-7-5-2>，因為<2,5> ∈ L−(6, 7) 、<5,4>  ∈ L−(5, 5)、<7,3>  ∈ L−/＋(3, 4)、<3,2>  ∈ L＋(2, 2) 和 <3,1>  ∈ L＋(1, 1) 是關鍵的2元組。最後LCaWSt的第一段<3-2-7>為近乎遞增段且第二段<7-5-2>為近乎遞減段，這符合T的前綴。


    資助

    這項研究工作得到台灣國家科學技術委員會根據合約 MOST 111-2221-E-110-034 的部分支持。


    相關文章

    1. 跨科仔準備與分析中山資工所的過程
    2. 中山資工所 找教授｜柯正雯、楊昌彪、程正傑
    3. 從生科轉資工的初期過程｜十個問答
    4. 生科轉資工1：一年表現狀況
    5. 生科轉資工2：二年表現狀況1
    6. 生科轉資工2：二年表現狀況2
    7. 碩論：最長共同近乎波動子序列問題 1
    8. 碩論：最長共同近乎波動子序列問題 2
    9. 生科轉資工3：入職趨勢一週年1
    10. 生科轉資工3：入職趨勢一週年2


    參考資料

    1. 呂宗霖。2023年。最長共同近乎波動子序列問題。臺灣碩博士論文知識加值系統
    2. Lu, Tsung-Lin, Kuo-Si Huang, and Chang-Biau Yang. "An Algorithm for Finding the Longest Common Almost Wave Subsequence with the Trend." 2023 14th IIAI International Congress on Advanced Applied Informatics (IIAI-AAI). IEEE, 2023.
    3. 演算法與計算理論學會。2024年。2023年最佳碩士論文優等獎：最長共同近乎波動子序列問題


    引用文獻

    1. [1] M. R. Alam and M. S. Rahman, "A divide and conquer approach and a work-optimal parallel algorithm for the lis problem," Information Processing Letters, Vol. 113, No. 13, pp. 470-476, 2013.
    2. [2] S. Bespamyatnikh and M. Segal, "Enumerating longest increasing subsequences and patience sorting," Information Processing Letters, Vol. 76, No. 1-2, pp. 7-11, 2000.
    3. [3] M. T. H. Bhuiyan, M. R. Alam, and M. S. Rahman, "Computing the longest common almost-increasing subsequence," Theoretical Computer Science, Vol. 930, pp. 157-178, 2022.
    4. [4] Y.-C. Chang and C.-B. Yang, "The longest common wave subsequence problem," The 38th Workshop on Combinatorial Mathematics and Computation Theory, Taipei, Taiwan, pp. 9-17, 2021.
    5. [5] G.-Z. Chen and C.-B. Yang, "The longest wave subsequence problem: Generalizations of the longest increasing subsequence problem," The 37th Workshop on Combinatorial Mathematics and Computation Theory, Kaohsiung, Taiwan, pp. 28-33, 2020.
    6. [6] M. Crochemore and E. Porat, "Fast computation of a longest increasing subsequence and application," Information and Computation, Vol. 208, No. 9, pp. 1054-1059, 2010.
    7. [7] A. L. Delcher, S. Kasif, R. D. Fleischmann, J. Peterson, O. White, and S. L. Salzberg, "Alignment of whole genomes," Nucleic Acids Research, Vol. 27, No. 11, pp. 2369-2376, 1999.
    8. [8] A. Elmasry, "The longest almost-increasing subsequence," Information Processing Letters, Vol. 110, No. 16, pp. 655-658, 2010.
    9. [9] J. W. Hunt and T. G. Szymanski, "A fast algorithm for computing longest common subsequences," Communications of the ACM, Vol. 20, pp. 350-353, 1977.
    10. [10] A. Khelassi1, S.-N. Yelles-Chaouche, and F. Benais, "Multi-arrhythmias detection with an XML rule-based system from 12-Lead Electrocardiogram," Electronic Physician, Vol. 9, pp. 4357-4363, 2017.
    11. [11] S.-C. Lin, "The longest almost wave subsequence problem," Master''s Thesis, Department of Computer Science and Engineering, National Sun Yat-sen University, Kaohsiung, Taiwan, 2022.
    12. [12] S.-F. Lo, K.-T. Tseng, C.-B. Yang, and K.-S. Huang, "A diagonal-based algorithm for the longest common increasing subsequence problem," Theoretical Computer Science, Vol. 815, pp. 69-78, 2020.
    13. [13] J. M. Moosa, M. S. Rahman, and F. T. Zohora, "Computing a longest common subsequence that is almost increasing on sequences having no repeated elements," Journal of Discrete Algorithms, Vol. 20, pp. 12-20, 2013.
    14. [14] C. Schensted, "Longest increasing and decreasing subsequences," Canadian Journal of Mathematics, Vol. 13, pp. 179-191, 1961.
    15. [15] T. T. Ta, Y.-K. Shieh, and C. L. Lu, "Computing a longest common almost-increasing subsequence of two sequences," Theoretical Computer Science, Vol. 854, pp. 44-51, 2021.
    16. [16] P. van Emde Boas, R. Kaas, and E. Zijlstra, "Design and implementation of an efficient priority queue," Mathematical Systems Theory, Vol. 10, No. 1, pp. 99-127, 1976.
    17. [17] I.-H. Yang, C.-P. Huang, and K.-M. Chao, "A fast algorithm for computing a longest common increasing subsequence," Information Processing Letters, Vol. 93, No. 5, pp. 249-253, 2005.

    留言

    張貼留言