rosalind/long.py at main · codeguru42/rosalind · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
from rosalind import parse_fasta


def prefixes(s):
    n = len(s)
    for i in range(n + 1):
        yield s[: n - i]


def test_prefixes():
    result = list(prefixes("ATTAGACCTG"))
    expected = [
        "ATTAGACCTG",
        "ATTAGACCT",
        "ATTAGACC",
        "ATTAGAC",
        "ATTAGA",
        "ATTAG",
        "ATTA",
        "ATT",
        "AT",
        "A",
        "",
    ]
    assert result == expected


def suffixes(s):
    n = len(s)
    for i in range(n + 1):
        yield s[i:]


def test_suffixes():
    result = list(suffixes("ATTAGACCTG"))
    expected = [
        "ATTAGACCTG",
        "TTAGACCTG",
        "TAGACCTG",
        "AGACCTG",
        "GACCTG",
        "ACCTG",
        "CCTG",
        "CTG",
        "TG",
        "G",
        "",
    ]
    assert result == expected


def most_overlapping_pair(dnas):
    max_a = ""
    max_b = ""
    max_overlap = ""
    for a in dnas:
        for b in dnas:
            if a != b:
                for suff in suffixes(a):
                    pre = b[: len(suff)]
                    if suff == pre and len(pre) > len(max_overlap):
                        max_a = a
                        max_b = b
                        max_overlap = pre
                        break
    return max_a, max_b, max_overlap


def test_most_overlapping_pair():
    dnas = [
        "ATTAGACCTG",
        "CCTGCCGGAA",
        "AGACCTGCCG",
        "GCCGGAATAC",
    ]
    result = most_overlapping_pair(dnas)
    expected = (
        "ATTAGACCTG",
        "AGACCTGCCG",
        "AGACCTG",
    )
    assert result == expected


def long(dnas):
    temp = dnas.copy()
    while len(temp) > 1:
        a, b, overlap = most_overlapping_pair(temp)
        temp.remove(a)
        temp.remove(b)
        temp.append(a + b[len(overlap) :])
    return temp[0]


def test_long():
    dnas = [
        "ATTAGACCTG",
        "CCTGCCGGAA",
        "AGACCTGCCG",
        "GCCGGAATAC",
    ]
    result = long(dnas)
    expected = "ATTAGACCTGCCGGAATAC"
    assert result == expected


def main():
    with open("rosalind_long.txt") as file:
        fasta = parse_fasta(file)
        print(long(list(fasta)))


if __name__ == "__main__":
    main()