Genome Assembly as Shortest Superstring

http://rosalind.info/problems/long/

Bioinformatics contest 2019의 Final Round의 4번문제인 Minimal Genom이 생각나는 문제였다.

Dynamic을 쓸 수 있을것 같아 보이지만 그렇지 않다. 선택이나 그런게 아닌 모든 경우의 수를 생각해야하는 np complete 문제이기 때문이다.

from util.read import read_fasta

def weld_seq(seq1, seq2):
    for weld_len in reversed(range(min(len(seq1), len(seq2)))):
        if seq1[-weld_len:] == seq2[0: weld_len]:
            return seq1 + seq2[weld_len:]
    return seq1 + seq2

seqs = list(map(lambda fasta: fasta[1], read_fasta('rosalind_long.txt')))

while len(seqs) > 1:
    weld_result = []
    for seq1 in seqs:
        for seq2 in seqs:
            if seq1 == seq2:
                continue
            welded_seq = weld_seq(seq1, seq2)
            score = abs(len(seq1) + len(seq2) - len(welded_seq))
            weld_result.append([seq1, seq2, welded_seq, score])
    max_weld = max(weld_result, key = lambda x: x[3])
    seqs.remove(max_weld[0])
    seqs.remove(max_weld[1])
    seqs.append(max_weld[2])
print(seqs[0])
pass

그냥 seqs의 길이가 1이 될때까지 가장 많이 겹치는 두 seq를 weld한다. 문제에서 there exists a unique way to reconstruct the entire chromosome from these reads by gluing together pairs of reads that overlap by more than half their length. 라고 돼있으므로 그냥 가장 많이 겹치는 두개를 합치면 된다.