Algorytm Smitha-Watermana (SW) jest typową techniką lokalnego dopasowywania sekwencji w biologii obliczeniowej. w biologii obliczeniowej. Jednak algorytm SW nie uwzględnia lokalnych zachowań aminokwasów, co może skutkować utratą niektórych użytecznych informacji. informacji. Zainspirowany sukcesem metody Markov Edit Distance (MED), niniejszy artykuł w związku z tym proponuje nową metodę Markov pairwise protein sequence alignment (MPPSA), która uwzględnia lokalne zależności kontekstowe. Wyniki wyniki numeryczne wykazały jej wyższość nad SW dla porównywania sekwencji białek. porównania sekwencji białek. --- TŁO: Ze względu na wysoką czułość, algorytm Smitha-Watermana jest szeroko używany do przeszukiwania biologicznych baz danych. Niestety, kwadratowa złożoność czasowa złożoność czasowa tego algorytmu sprawia, że jest on bardzo czasochłonny. Wykładniczy wykładniczy wzrost biologicznych baz danych dodatkowo pogarsza sytuację. Aby przyspieszyć tego algorytmu, podjęto wiele wysiłków w celu opracowania technik w architekturach o wysokiej wydajnych architekturach, w szczególności ostatnio pojawiających się architekturach wielordzeniowych architekturach wielordzeniowych i związanych z nimi modelach programowania. WYNIKI: Niniejszy artykuł opisuje najnowszą wersję oprogramowania CUDASW++, CUDASW++ 2.0, która wnosi nowy wkład do białkowej bazy danych Smitha-Watermana Smitha-Watermana przy użyciu zunifikowanej architektury obliczeniowej (CUDA). Równoległy algorytm Smitha-Watermana w celu dalszej optymalizacji wydajności algorytmu CUDASW++ 1.0 w oparciu o abstrakcję pojedynczej instrukcji, wielu wątków (SIMT) abstrakcji. Po raz pierwszy zbadaliśmy partycjonowany wektorowy algorytm Smitha-Watermana przy użyciu CUDA w oparciu o zwirtualizowaną abstrakcję pojedynczej instrukcji, wielu danych (SIMD). Zoptymalizowane algorytmy SIMT i partycjonowane wektoryzowane algorytmy zostały poddane testom porównawczym i, co ciekawe, mają podobną wydajność. charakterystykę. CUDASW++ 2.0 osiąga poprawę wydajności w stosunku do CUDASW++ 1.0 aż 1,74 (1,72) razy przy użyciu zoptymalizowanego algorytmu SIMT i do 1,77 (1,66) razy przy użyciu partycjonowanego algorytmu wektorowego, z wydajnością do 17 (30) miliardów aktualizacji komórek na sekundę (GCUPS) na karcie graficznej GeForce GTX 280 (dual-GPU GeForce GTX 295). WNIOSKI: CUDASW++ 2.0 jest publicznie dostępnym oprogramowaniem open-source, napisanym w językach programowania CUDA i językach programowania C++. Uzyskuje znaczną poprawę wydajności w porównaniu do CUDASW++ 1.0 przy użyciu zoptymalizowanego algorytmu SIMT lub partycjonowany algorytm wektorowy do przeszukiwania białkowej bazy danych Smitha-Watermana poprzez w pełni wykorzystując możliwości obliczeniowe powszechnie stosowanych tanich procesorów graficznych z obsługą CUDA. procesorów graficznych. --- Problem znalezienia optymalnego dopasowania strukturalnego dla pary nakładających się białek jest często podatny na algorytm programowania dynamicznego Smitha-Watermana. Smitha-Watermana, który działa w czasie proporcjonalnym do iloczynu długości dopasowywanych sekwencji. Podczas gdy kwadratowy czas działania jest akceptowalny do obliczenia pojedynczego dopasowania dwóch stałych struktur białkowych, złożoność czasowa staje się wąskim gardłem, gdy złożoność staje się wąskim gardłem podczas wielokrotnego uruchamiania procedury Smitha-Watermana w celu znalezienia globalnie optymalnej superpozycji i wyrównania białek wejściowych. białek wejściowych. Przedstawiamy algorytm o subkwadratowym czasie działania, zdolny do obliczyć dopasowanie, które optymalizuje jedną z najczęściej stosowanych miar podobieństwa struktury białek, zdefiniowaną jako liczba par reszt w dwóch białkach, które można nałożyć na siebie. białek, które można nałożyć na siebie w ramach predefiniowanego odcięcia odległości. Algorytm Algorytm przedstawiony w tym artykule może być wykorzystany do znacznej poprawy w wielu popularnych metodach dopasowywania struktur białkowych. struktur białkowych. --- Czułość i selektywność algorytmów porównywania sekwencji białek FASTA i Smith-Waterman i Smitha-Watermana zostały ocenione przy użyciu klasyfikacji nadrodzin w bazie danych sekwencji białek National Biomedical Research Foundation/Protein Biomedical Research Foundation/Protein Identification Resource (PIR). Sekwencje z każdej z 34 nadrodzin w bazie danych PIR z 20 lub więcej członkami zostały porównane z bazą danych sekwencji białek. Wyniki podobieństwa powiązanych i niepowiązanych sekwencji i niepowiązanych sekwencji zostały określone przy użyciu programu FASTA lub algorytmu Smitha-Watermana. Te dwa zestawy wyników podobieństwa zostały wykorzystane do oceny zdolności dwóch algorytmów porównawczych do identyfikacji odległych sekwencji białkowych. Program FASTA wykorzystujący ustawienie czułości ktup = 2 działał równie dobrze jak algorytm Smitha-Watermana dla 19 z 34 nadrodzin. 34 superrodzin. Zwiększenie czułości poprzez ustawienie ktup = 1 pozwoliło programowi FASTA działał równie dobrze jak Smith-Waterman w przypadku dodatkowych 7 nadrodzin. The rygorystyczna metoda Smitha-Watermana działała lepiej niż FASTA z ktup = 1 dla 8 superrodzin nadrodzin, w tym globin, regionów zmiennych immunoglobulin, kalmoduliny i plastocyjaniny. Zbadano kilka strategii poprawy czułości FASTA. Największą poprawę czułości osiągnięto poprzez optymalizację pasma wokół najlepszego regionu początkowego znalezionego dla każdej sekwencji biblioteki. sekwencji. Dla każdej nadrodziny z wyjątkiem globin i zmiennych regionów immunoglobulin ta strategia była tak samo czuła jak pełna Smith-Waterman. Dla niektórych sekwencji sekwencji, dodatkową czułość osiągnięto poprzez włączenie konserwatywnych, ale ale nieidentycznych reszt w tabeli wyszukiwania używanej do identyfikacji regionu początkowego. --- Algorytm Smitha-Watermana do lokalnego dopasowywania sekwencji jest jedną z najważniejszych technik obliczeniowej biologii molekularnej. najważniejszych technik w obliczeniowej biologii molekularnej. To genialne dynamiczne dynamiczne zostało zaprojektowane w celu ujawnienia wysoce konserwatywnych fragmentów poprzez odrzucając słabo konserwowane segmenty początkowe i końcowe. Jednak istniejące podobieństwa lokalnego ma poważną wadę: nie odrzuca słabo konserwowanych segmentów pośrednich. konserwowanych segmentów pośrednich. Algorytm Smitha-Watermana znajduje lokalne dopasowanie z maksymalnym wynikiem, ale nie jest w stanie znaleźć lokalnego dopasowania z maksymalny stopień podobieństwa (np. maksymalny procent dopasowań). Co więcej, nie ma nadal nie ma wydajnego algorytmu, który odpowiadałby na następujące naturalne pytanie: czy dwie sekwencje dzielą (wystarczająco długi) fragment z ponad 70% podobieństwa? podobieństwa? W rezultacie lokalne dopasowanie czasami tworzy mozaikę dobrze zachowanych fragmentów sztucznie połączonych przez słabo zachowane lub nawet niepowiązanymi fragmentami. Może to prowadzić do problemów z porównywaniem długich sekwencji genomowych i przewidywaniem genów porównawczych. sekwencji genomowych i przewidywania genów porównawczych, na co ostatnio zwrócili uwagę Zhang i wsp. al. (Bioinformatics, 15, 1012-1019, 1999). W tym artykule proponujemy nowy algorytm algorytm porównywania sekwencji (znormalizowane wyrównanie lokalne), który zgłasza regiony o maksymalnym stopniu podobieństwa. regiony o maksymalnym stopniu podobieństwa. Algorytm jest oparty na programowaniu ułamkowym a jego czas działania wynosi O(n2log n). W praktyce, znormalizowane lokalne jest tylko 3-5 razy wolniejszy niż standardowy algorytm Smitha-Watermana. --- Przeszukiwanie bazy danych pod kątem lokalnego dopasowania do zapytania w ramach typowego schematu punktacji PAM120 lub BLOSUM62 z afinicznymi kosztami luk, jest obliczeniem, które oparło się algorytmicznej poprawie ze względu na swoją podstawę w programowaniu dynamicznym i słabą naturę wyszukiwanych sygnałów. Na etapie wstępnego przetwarzania zapytania zapytania można zbudować zestaw tabel, które pozwalają (a) wyeliminować dużą (a) wyeliminować dużą część macierzy programowania dynamicznego z rozważań i (b) obliczyć kilku kroków pozostałej części za pomocą pojedynczego wyszukiwania w tabeli. Chociaż wynik ten jest nie jest asymptotyczną poprawą w stosunku do oryginalnego algorytmu Smitha-Watermana, jego złożoność jest scharakteryzowana w kategoriach niektórych rzadkich cech macierzy i daje najszybszą jak dotąd implementację oprogramowania dla takich wyszukiwań.
Jaki jest czas wykonania (złożoność) algorytmu Smitha-Watermana dla wyrównania dwóch sekwencji
Złożoność algorytmu programowania dynamicznego Smitha-Watermana jest kwadratowa, co oznacza, że działa on w czasie proporcjonalnym do iloczynu długości porównywanych sekwencji.