BioInformaticsAlgorithms/ReconstructStringFromKmer.py at master · Andrewwu73/BioInformaticsAlgorithms · 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
kmers = []
lenerBoi = int(input(""))
a = "nice"
while len(a)>1:
    a = input("")
    if(len(a)>1):
        kmers.append(a)
graph = {}
for m in kmers:
    prefix = m[0:len(m)-1]
    suffix = m[1:len(m)]
    if(prefix in graph):
        graph[prefix] = graph[prefix]+[suffix]
    else:
        graph[prefix] = [suffix]


import random

toAdd = []
for unlucky in graph:
    for m in graph[unlucky]:
        if(m not in graph):
            toAdd.append(m)
for l in toAdd:
    graph[l] = []
oddDegree = []
degreeDictionary = {}
for m in graph:
    if(m not in degreeDictionary):
        degreeDictionary[m] = len(graph[m])
    else:
        degreeDictionary[m] = degreeDictionary[m]+len(graph[m])
    for j in graph[m]:
        if(j not in degreeDictionary):
            degreeDictionary[j] = 1
        else:
            degreeDictionary[j] = degreeDictionary[j]+1
for l in degreeDictionary:
    if(degreeDictionary[l]%2==1):
        oddDegree.append(l)
x = random.randint(0,1)
current = oddDegree[x]
if(len(graph[current])==0):
    current = oddDegree[(x-1)%2]
answer = []
path = [current]
startPossible = []
while(len(graph[current])>0):
    chooseNext = random.randint(1, len(graph[current]))-1
    path.append(graph[current][chooseNext])
    answer.append((current, graph[current][chooseNext]))

    current = graph[current].pop(chooseNext)

def checkExplored(graph):
    for m in graph:
        if(len(graph[m])>0):
            return False
    return True
for xd in path:
    if(len(graph[xd])>0):
        startPossible.append(xd)
while(not checkExplored(graph)):
    newCurrent = startPossible[random.randint(0, len(startPossible)-1)]
    temp = newCurrent
    cycle = []
    cycleNodes = [newCurrent]

    while(len(graph[newCurrent])>0):
        chooseNext = random.randint(1, len(graph[newCurrent]))-1
        cycle.append((newCurrent, graph[newCurrent][chooseNext]))
        if(len(graph[newCurrent])==1 and newCurrent in startPossible):
            startPossible.remove(newCurrent)
        if(graph[newCurrent][chooseNext] not in path):
            path.append(graph[newCurrent][chooseNext])
        newCurrent = graph[newCurrent].pop(chooseNext)
        cycleNodes.append(newCurrent)
    done = False
    for l in range(len(answer)):
        if(answer[l][0]==temp and done == False):
            for m in range(len(cycle)):
                answer.insert(l+m, cycle[m])
            done = True
        elif(answer[l][1]==temp and done == False):
            for m in range(len(cycle)):
                answer.insert(l+m+1, cycle[m])
            done = True
    for xd in path:
        if(len(graph[xd])>0 and (xd not in startPossible)):
            startPossible.append(xd)
ans = answer[0][0]
for m in range(len(answer)):
    ans = ans + answer[m][1][lenerBoi-2]

f = open('reconstructString.txt', 'w')
f.write(ans)
f.close()