Scalanie fragmentów DNA

0

Witam wszystkich,
otóż mam taki problem, dostaję przykład sekwencji DNA - GACACCATC, potem rozcinam to, ale w różnych miejscach i otrzymuję mniejsze sekwencje:

  • GACA
  • CACCA
  • CATC
    I tu moja prośba o jakieś wskazówki jak się za to zabrać, by połączyć te mniejsze sekwencje w pierwotny łańcuch? Jak widać, w każdym fragmencie się powtarzają litery z innego fragmentu, więc trzeba nadmiarowe usunąć i połączyć wyczyszczone sekwencje. Mogę otrzymać też same porozcinane fragmenty bez pierwotnej sekwencji, bo też mogę mieć taką sytuację. To jak poradzić sobie z takim problemem i np. mogę dostać o wiele dłuższe fragmenty i też będą zawierać fragmenty innych sekwencji abym mógł je scalić w jedność. Czyli dajmy mam 10 wycinków, przykładowy pierwszy, długi wycinek ma 10 literek na końcu, które są początkiem drugiego wycinka. Czyli wiem, że to na pewno będą wycinki do scalenia. Jak zabrać się za to programując?
    To co ja myślę:
  • posortowałbym łańcuchy według długości
  • potem sprawdzałbym od najmniejszego łancucha czy występuje w największym
print( 'cale', "GACA" in  "CACCA" )  # False
  • potem porwónywałbym znaki na odpowiednim miejscu
a = 3
print( a, "CACCA"[-a:] == "GACA"[:a] )
 
a = 2
print( a, "CACCA"[-a:] == "GACA"[:a] )
 
a = 1
print( a, "CACCA"[-a:] == "GACA"[:a] )

No i wsadziłbym to w pętle i dodawał do stringa jeśli zwracałoby mi True, nie wiem czy dobrze myślę i czy nie pod górkę.

0

Czyli wiem, że to na pewno będą wycinki do scalenia.

Bzdura. To że ci sie prefix/suffix powtórzy wcale nie znaczy że coś do siebie pasuje.
No ale możesz próbować to tak dopasować algorytmem zachłannym -> bierzesz dany ciąg i szukasz jego suffixu jako prefixu innych ciągów i wybierasz opcje która będzie najdłuższa. Zaczynałbym od całego ciągu a potem skracał o 1 aż się trafi dopasowanie.
Dodatkowo powinieneś najpierw wyliczyć to dla wszystkich ciągów po kolei a potem dopiero wybrać jak będziesz dopasowywał. Bo moze tak być że ciąg X pasuje w 2 miejsca ale ciąg Y pasuje tylko w jedno z tych miejsc. W efekcie jak wrzucisz tam X to Y nie będzie miał juz dopasowania.

1 użytkowników online, w tym zalogowanych: 0, gości: 1