Partial Digest Problem - один из алгоритмов получения мест среза в ДНК.Учитывая все возможные длины реза, например [2,2,3,3,4,5,6,7,8,10], я должен найти способ найти реальные места реза.В этом примере общая длина ДНК равна 10, а места фактического разреза - [0,3,6,8,10].
Из алгоритма, приведенного выше, я пытаюсь построить реальный код на python, и со стороны я не уверен, что ясделано неправильно.Желаемым выводом для этого кода является [0,3,6,8,10], где я получаю только «Нет». Может кто-нибудь сказать, какая часть в моем коде неверна?
# function to remove multiple elements given as list
def delete(elements,A):
for el in elements:
A.remove(el)
return A
# y is given as integer, X as list
def delta(y,X):
n = len(X)
for i in range(n):
X[i] -= y
X[i] = abs(X[i])
return sorted(X)
# If former contains latter, return true. Else, return false
def contains(small, big):
for i in range(len(big)-len(small)+1):
for j in range(len(small)):
if big[i+j] != small[j]:
break
else:
return True
return False
def partialDigest(L):
global width
width = (max(L))
delete([width], L) # Needs to be in list to feed to 'delete' function
X = [0, width]
X = place(L,X)
return X
def place(L,X):
if len(L) == 0: # Baseline condition
return X
y = max(L)
if contains(delta(y,X),L): # If former is the subset of L
delete(delta(y,X), L) # Remove lengths from L
X += list(y) # assert that this y is one of the fixed points, X
X = sorted(X) # To maintain order
print(X)
place(L,X) # Recursive call of the function to redo the upper part
# If none of the if statements match the condition, continue
X.remove(y) # If the code reaches down here, it means the assumption that
# y is one of the points is wrong. Thus undo
L += delta(y,X) # undo L
L = sorted(L) # To maintain order
# Do the same thing except this time it's (width-y)
elif contains(delta(width-y,X),L):
delete(delta(width-y,X), L)
X += list(width - y)
X = sorted(X)
place(L,X)
X.remove(width-y)
L += delta(y,X)
L = sorted(L)
L = [2,2,3,3,4,5,6,7,8,10]
X = partialDigest(L)
print(X)