Zadanie 3: Algorytm Allisona - allison (3 pkt)
Zaimplementuj algorytm Allisona do znajdowania optymalnego globalnego wyrównania:
def allison_global_alignment(s1: str, s2: str,
match_score: int = 2,
mismatch_score: int = -1,
gap_penalty: int = -1) -> tuple[int, str, str]:
"""
Znajduje optymalne globalne wyrównanie używając algorytmu Allisona.
Args:
s1: Pierwszy ciąg znaków
s2: Drugi ciąg znaków
match_score: Punkty za dopasowanie
mismatch_score: Punkty za niedopasowanie
gap_penalty: Kara za lukę
Returns:
Krotka zawierająca wynik wyrównania i dwa wyrównane ciągi
"""
pass
def allison_local_alignment(s1: str, s2: str,
match_score: int = 2,
mismatch_score: int = -1,
gap_penalty: int = -1) -> tuple[int, str, str, int, int]:
"""
Znajduje optymalne lokalne wyrównanie (podobnie do algorytmu Smith-Waterman).
Args:
s1: Pierwszy ciąg znaków
s2: Drugi ciąg znaków
match_score: Punkty za dopasowanie
mismatch_score: Punkty za niedopasowanie
gap_penalty: Kara za lukę
Returns:
Krotka zawierająca wynik wyrównania, dwa wyrównane ciągi oraz pozycje początku
"""
passTwoje zadanie:
- Zaimplementuj algorytm Allisona dla globalnego wyrównania
- Zaimplementuj wersję dla lokalnego wyrównania
- Obsłuż różne systemy punktacji (dopasowanie, niedopasowanie, luki)
- Zwróć uwagę na różnice między wyrównaniem globalnym a lokalnym
Przykład:
s1 = "ACGTACGT"
s2 = "ACGTGCGT"
allison_global_alignment(s1, s2) = (13, "ACGT-ACGT", "ACGTGCGT-")Last updated on