Day26 | Rosalind 生資解題 - 014. LCSM（Finding a Shared Motif）最長子字串比對 - 下篇

延續前一天的內容
我們來繼續優化絲路之旅

解法三：二分搜尋長度、set()取交集

在解題前，我們先寫一個產生器
若輸入一段字串，則產生所有長度L的排列組合

def _substrings_of_length(s: str, L: int) -> Set[str]:
    return {s[i:i+L] for i in range(len(s) - L + 1)} if L > 0 else {""}

print(_substrings_of_length("TTAGGG", 4)) # {'TTAG', 'TAGG', 'AGGG'}

接著，解題思路如下：

若存在某個長度為 L 的共同子字串，那麼所有 ≤L 的長度一定也存在
反之，若 L 不存在，則共同子字串長度 >L 就更不可能存在
以及，如果有存在共同子字串 => 則對應長度的交集非空

二分法的意思是
舉例：L長度為5，我們先測試長度2（取mid中間值）是否符合
如果長度2有符合的話，下一次就往2+1=3來做嘗試
如果長度2不符合的話，下一次就往2-1=1來做嘗試

非常的繞彎，要把大腦轉個720度看會不會好一些
老實講，把二分法運用在這裡，能想到這種解法真的非常牛逼！

首先
依然是挑最短的序列作為模板，接著對長度L（此模板）做二分搜尋
（因為不存在比此序列更大的子字串，L就是最長的上限）
對每個字串把所有長度為L的子字串做成set，再逐步用and operator相交
非空集合就代表有匹配，可以往更長的模板來試

from typing import Dict, Iterable, Set, List

def parse_fasta(data: str) -> Dict[str, str]:
    sequences = {}
    label = ""
    for line in data.strip().splitlines():
        line = line.strip()
        if not line:
            continue
        if line.startswith(">"):
            label = line[1:].strip()
            if not label:
                label = ""
                continue
            sequences[label] = ""
        elif label:
            sequences[label] += line
    return sequences

def _substrings_of_length(s: str, L: int) -> Set[str]:
    return {s[i:i+L] for i in range(len(s) - L + 1)} if L > 0 else {""}

def longest_common_substrings(seqs: Dict[str, str]) -> List[str]:
    if not seqs:
        return []
    s_seq = min(seqs.values(), key=len) # 最短字串作為模板
    low, high = 0, len(s_seq)  # 二分搜尋長度
    best_set: Set[str] = set()

    while low <= high:
        mid = (low + high) // 2
        inter = _substrings_of_length(s_seq, mid)

        if not inter: # 空集合的話
            high = mid - 1
            continue

        # 與其餘字串的同長度子字串集合相交
        for s in list(seqs.values())[1:]:
            if not inter:
                break
            inter &= _substrings_of_length(s, mid)
        if inter: # 有交集的話
            best_set = inter
            low = mid + 1      # 嘗試更長序列
        else:
            high = mid - 1      # 序列太長，縮短

    return sorted(best_set) # 回傳sorted後的陣列（原先是set，排序過後變成陣列）

data = """
>Rosalind_1
GATTACA
>Rosalind_2
TAGACCA
>Rosalind_3
ATACA
"""

seqs = parse_fasta(data)
print(longest_common_substrings(seqs))  # ['AC', 'CA', 'TA']