SPA (oprogramowanie)
| Deweloper (y) |
Uniwersytet Państwowy w Petersburgu , Rosja Uniwersytet Akademicki w Petersburgu , Rosja Uniwersytet Kalifornijski, San Diego , USA |
|---|---|
| Wersja stabilna | 3.15.2 / 8 marca 2021 r |
| Magazyn | |
| System operacyjny | Linux, Mac OS |
| Typ | Bioinformatyka |
| Licencja | bezpłatne korzystanie |
| Strona internetowa | cab.spbu.ru/software/spades/ |
SPAdes ( asembler genomu z St. Petersburga) to algorytm składania genomu , który został zaprojektowany dla zestawów danych bakteryjnych jednokomórkowych i wielokomórkowych . Dlatego może nie nadawać się do dużych projektów genomów.
SPAdes współpracuje z Ion Torrent , PacBio , Oxford Nanopore i Illumina z parami końcówek, parami mate i pojedynczymi odczytami . SPAdes zostało zintegrowane z Galaxy przez Guya Lionela i Philipa Mabona.
Tło
Badanie genomu pojedynczych komórek pomoże śledzić zmiany zachodzące w DNA w czasie lub związane z narażeniem na różne warunki. Ponadto sekwencjonowanie pojedynczych komórek (SCS) przyniosłoby ogromne korzyści w przypadku wielu projektów, takich jak projekt ludzkiego mikrobiomu i odkrycie antybiotyków . SCS ma przewagę nad sekwencjonowaniem DNA ekstrahowanego z dużej liczby komórek. Problem uśredniania znaczących zmian między komórkami można pokonać za pomocą SCS. Technologie eksperymentalne i obliczeniowe są optymalizowane, aby umożliwić naukowcom sekwencjonowanie pojedynczych komórek. Na przykład amplifikacja DNA wyekstrahowanego z pojedynczej komórki jest jednym z wyzwań eksperymentalnych. Aby zmaksymalizować dokładność i jakość SCS, konieczna jest jednolita amplifikacja DNA. Wykazano, że zastosowanie cykli wielokrotnej hybrydyzacji i amplifikacji opartej na pętli ( MALBAC ) do amplifikacji DNA generuje mniej błędu systematycznego w porównaniu z reakcją łańcuchową polimerazy ( PCR ) lub amplifikacją z wielokrotnym wypieraniem (MDA). Ponadto uznano, że wyzwania stojące przed SCS mają charakter obliczeniowy, a nie eksperymentalny. Obecnie dostępne asemblery, takie jak Velvet , String Graph Assembler (SGA) i EULER-SR, nie zostały zaprojektowane do obsługi montażu SCS. Montaż danych pojedynczej komórki jest trudny ze względu na nierównomierny zasięg odczytu, różnice w długości wstawki, wysoki poziom błędów sekwencjonowania i odczyty chimeryczne . Dlatego nowe podejście algorytmiczne, SPAdes, zostało zaprojektowane, aby rozwiązać te problemy.
Podejście montażowe SPAdes
SPAdes wykorzystuje k-mery do budowy początkowego grafu de Bruijna i w kolejnych etapach wykonuje operacje grafowo-teoretyczne, które opierają się na strukturze grafu, pokryciu i długościach sekwencji. Co więcej, koryguje błędy iteracyjnie. Etapy montażu w SPAdesach to:
- Etap 1: budowa wykresu montażowego. SPAdes wykorzystuje wielowymiarowy wykres de Bruijna (patrz poniżej), który wykrywa i usuwa odczyty wybrzuszeń/pęcherzyków i chimerów.
- Etap 2: dostosowanie k-bimerów (par k-merów). Oszacowano dokładne odległości między k-merami w genomie (krawędzie na wykresie składania).
- Etap 3: konstrukcja wykresu złożenia sparowanego.
- Etap 4: konstrukcja ciągła. SPAdes wyprowadza kontigi i umożliwia mapowanie odczytów z powrotem na ich pozycje na wykresie złożenia po uproszczeniu wykresu (backtracking).
Szczegóły dotyczące montażu SPAdes
SPAdes został zaprojektowany w celu przezwyciężenia problemów związanych z montażem danych z pojedynczej komórki w następujący sposób:
1. Niejednolity zasięg . SPAdes wykorzystuje wielowymiarowy graf de Bruijna, który pozwala na zastosowanie różnych wartości k. Sugerowano użycie mniejszych wartości k w obszarach o niskim pokryciu, aby zminimalizować fragmentację, i większych wartości k w obszarach o dużym pokryciu, aby zmniejszyć zapadanie się powtórzeń (etap 1 powyżej).
2. Zmienne rozmiary wkładek odczytów ze sparowanych końców . SPAdes wykorzystuje podstawową koncepcję sparowanych grafów de Bruijna. Jednak sparowany de Bruijn działa dobrze w przypadku odczytów ze sparowanych końców ze stałym rozmiarem wstawki. Dlatego SPAdes szacuje „odległości” zamiast używać „rozmiarów płytek”. Odległość (d) odczytu na sparowanych końcach definiuje się jako, dla długości odczytu L, d = rozmiar wkładki – L. Stosując metodę dopasowania k-bimeru, odległości są dokładnie szacowane. K-bimer składający się z k-merów „α” i „β” wraz z szacunkową odległością między nimi w genomie (α|β,d). Podejście to dzieli odczyty sparowanych końców na pary k-merów, które są przekształcane w celu zdefiniowania par krawędzi (biedges) na wykresach de Bruijna. Te zbiory krawędzi biorą udział w estymacji odległości pomiędzy krawędziami ścieżek pomiędzy k-merami α i β. Poprzez grupowanie wybierane jest optymalne oszacowanie odległości z każdego skupienia (etap 2 powyżej). Aby skonstruować sparowany wykres de Bruijna, wykorzystuje się wykresy prostokątne w SPAdes (etap 3). Podejście oparte na wykresach prostokątnych zostało po raz pierwszy wprowadzone w 2012 roku w celu skonstruowania sparowanych wykresów de Bruijna z wątpliwymi odległościami.
3. Wybrzuszenie, końcówki i chimery . Wybrzuszenia i końcówki powstają w wyniku błędów odpowiednio w środku i na końcu odczytów. Połączenie chimeryczne łączy dwa niepowiązane ze sobą podciągi genomu. SPAdes identyfikuje je na podstawie topologii grafów, długości i pokrycia zawartych w nich nierozgałęzionych ścieżek. SPAdes utrzymuje strukturę danych, aby móc cofnąć wszystkie poprawki lub usunięcia.
SPAdes modyfikuje wcześniej stosowane podejście do usuwania wybrzuszeń i iteracyjne podejście do wykresów de Bruijna opracowane przez Penga i in. (2010) i tworzy nowe podejście zwane „korremowalem wybrzuszenia”, co oznacza korekcję i usuwanie wybrzuszeń. Algorytm usuwania wybrzuszeń można podsumować w następujący sposób: proste wybrzuszenie tworzone jest przez dwie małe i podobne ścieżki (P i Q) łączące te same węzły. Jeśli P jest ścieżką nierozgałęzioną (ścieżką h), wówczas SPAdes odwzorowuje każdą krawędź w P na rzut krawędzi w Q i usuwa P z grafu, w wyniku czego zwiększa się pokrycie Q. W przeciwieństwie do innych asemblerów, które stosują usuwanie wybrzuszeń o stałym pokryciu odcięcia, SPAdes krok po kroku usuwa lub wyświetla ścieżki h o niskim pokryciu. Osiąga się to poprzez zastosowanie stopniowo rosnących progów odcięcia i iterację przez wszystkie ścieżki h w rosnącej kolejności pokrycia (w celu usunięcia wybrzuszeń i usunięcia chimerów) lub długości (w celu usunięcia końcówki). Co więcej, aby zagwarantować, że do grafu nie zostaną wprowadzone żadne nowe źródła/ujścia, SPAdes usuwa ścieżkę h (w przypadku chimerycznego usuwania ścieżki h) lub projekty (w przypadku usuwania wybrzuszeń) tylko wtedy, gdy jej początek i koniec wierzchołki mają co najmniej dwie krawędzie wychodzącą i wchodzącą . Pomaga to usunąć ścieżki h o niskim pokryciu, powstałe w wyniku błędów sekwencjonowania i odczytów chimerycznych, ale nie z powtórzeń.
SPAdes potoki i wydajność
SPAdes składa się z następujących narzędzi:
- Przeczytaj narzędzie do korekcji błędów, BayesHammer (dla danych Illumina) i IonHammer (dla danych IonTorrent) . W tradycyjnej korekcji błędów rzadkie k-mery są uważane za błędy. Nie można tego zastosować w przypadku SCS ze względu na nierównomierny zasięg. Dlatego BayesHammer wykorzystuje probabilistyczne podgrupy, które badają wiele centralnych nukleotydów, które będą lepiej pokryte niż inne, podobnych k-merów. Twierdzono, że w przypadku jednokomórkowego zestawu danych Escherichia coli (E. coli) BayesHammer działa w około 75 minut, zajmuje do 10 Gb pamięci RAM na przeprowadzenie korekcji błędów odczytu i wymaga 10 Gb dodatkowego miejsca na dysku na pliki tymczasowe .
- Iteracyjny asembler genomu z krótkim odczytem, SPAdes . W przypadku tego samego zestawu danych ten etap trwa ~ 75 minut. Wykonanie etapu 1 zajmuje ~ 40% tego czasu (patrz podejście do montażu SPAdes powyżej) przy użyciu trzech iteracji (k=22, 34 i 56) oraz ~ 45%, 14% i 1% na ukończenie etapów 2, 3 i 4, odpowiednio. Montaż zajmuje również do 5 Gb pamięci RAM i wymaga 8 Gb dodatkowego miejsca na dysku.
- Korektor niedopasowań (wykorzystujący narzędzie BWA ). Moduł ten wymaga najdłuższego czasu (~120 min) i największej dodatkowej przestrzeni dyskowej (~21 Gb) na pliki tymczasowe. E. coli potrzeba do 9 Gb pamięci RAM .
- Moduł do składania wysoce polimorficznych genomów diploidalnych, dipSPAdes . dipSPAdes konstruuje dłuższe kontigi, wykorzystując rozbieżność między haplomami w powtarzalnych regionach genomu. Następnie wytwarza konstrukcję kontigów konsensusowych i składa haplotyp.
Porównanie asemblerów
W badaniu porównano kilka asemblerów genomu na próbkach pojedynczych komórek E. coli . Tymi asemblerami są EULER-SR, Velvet, SOAPdenovo, Velvet-SC, EULER+ Velvet-SC (E+V-SC), IDBA-UD i SPAdes. Wykazano, że najlepiej radzą sobie IDBA-UD i SPAdes. SPAdes miał największy NG50 (99 913, statystyki NG50 są takie same jak N50, z tym wyjątkiem, że używany jest rozmiar genomu, a nie rozmiar złożenia). Co więcej, wykorzystując E. coli , SPAdes zgromadziły najwyższy procent genomu (97%) i największą liczbę kompletnych genów (4071 z 4324). Występy montażystów przedstawiały się następująco:
- Liczba kontigów:
IDBA-UD < Velvet < E+V-SC < SPAdes < EULER-SR < Velvet-SC < SOAPdenovo
- NG50
SPAdes > IDBA-UD >>> E+V-SC > EULER-SR >Velvet >Velvet-SC > SOAPdenovo
- Największy kontig:
IDBA-UD > SPAdy > > EULER-SR > Velvet= E+V-SC > Velvet-SC > SOAPdenovo
- Zmapowany genom (%):
SPAdy > IDBA-UD > E+V-SC > Velvet-SC > EULER-SR > SOAPdenovo > Velvet
- Liczba błędnych montażu:
E+V-SC = Velvet = Velvet-SC < SOAPdenovo < IDBA-UD < SPADes < EULER-SR