Wyszukiwanie sekwencji podobnej do danej metodą BLAST
Witaj na stronie prezentującej działanie algorytmu BLAST wyszukiwania sekwencji podobnej do danej.
Przejdź do demonstracji »
Algorytm BLAST (Basic Local Aligment Search Tool) to heurystyczny algorytm porównywania sekwencji DNA lub białek.
Zazwyczaj sekwencje nukleotydów i aminokwasów są długie i porównywanie ich w całości ze znanymi wzorcami
jest zagadnieniem czasochłonnym i złożonym. Aby skrócić czas obliczeń, algorytm BLAST nie porównuje
całej zadanej sekwencji, lecz dzieli ją na krótsze fragmenty - słowa. Długość słów jest parametrem wejściowym algorytmu.
Kolejnym krokiem algorytmu jest wyszukanie tych rekordów bazy danych, w których występuje szukane słowo lub podobne do niego
(oznacza to wartość podobieństwa wyższą od zadanego progu T). W ostatnim kroku algorytm rozszerza ciągi referencyjne
(w prawo lub lewo) i ponownie dokonuje ich oceny. Rozszerzenie jest wykonywane do momentu aż ocena spadnie poniżej
progu podobieństwa. Wynikiem końcowym algorytmu są rekordy o największym podobieństwie do zadanej sekwencji.