SPAdes(소프트웨어)

SPAdes (software)
SPAdes
개발자러시아 상트페테르부르크 주립 대학교
러시아 상트페테르부르크 학술 대학교
캘리포니아 대학교 샌디에이고, 미국
안정된 릴리스
3.15.2 / 2021년 3월 8일
저장소
운영 체제Linux, Mac OS
유형생물정보학
면허증.자유 사용
웹 사이트cab.spbu.ru/software/spades/

SPAdes(St.Petersburg genome assembler)[1]는 단세포 및 다세포 세균 데이터 세트를 위해 설계된 게놈 조립 알고리즘입니다.따라서 대규모 게놈 [1][2]프로젝트에는 적합하지 않을 수 있습니다.

SPAdes는 Ion Torrent, Pac Bio, Oxford Nanopore 및 Illumina 쌍, 짝짝이 및 싱글 판독과 [1]함께 작동합니다.SPAdes는 Guy Lionel과 [3]Philip Mabon에 의해 갤럭시 파이프라인에 통합되었습니다.

배경

단세포의 게놈을 연구하는 것은 시간이 지남에 따라 또는 다른 조건에 노출되는 것과 관련된 DNA의 변화를 추적하는데 도움을 줄 것이다.또한 Human Microbiom Project 및 항생제 발견과 같은 많은 프로젝트는 단세포 염기서열 분석([4][5]SCS)의 혜택을 크게 받을 것입니다.SCS는 많은 세포에서 추출된 DNA의 염기서열 분석보다 유리합니다.셀 간의 상당한 차이를 평균화하는 문제는 [6]SCS를 사용하여 해결할 수 있습니다.실험 및 계산 기술은 연구자들이 단세포를 배열할 수 있도록 최적화되고 있다.예를 들어, 단일 세포에서 추출된 DNA의 증폭은 실험 과제 중 하나이다.SCS의 정확성과 품질을 극대화하려면 균일한 DNA 증폭이 필요합니다.DNA 증폭을 위해 다중 아닐링 및 루프 기반 증폭 주기(MALBAC)를 사용하면 중합효소 연쇄 반응(PCR) 또는 다중 치환 증폭(MDA)[7]에 비해 편향이 덜 발생하는 것으로 나타났다.또한 SCS가 직면한 과제는 [8]실험적인 것이 아니라 계산적인 것이라는 사실이 인정되었습니다.Velvet,[9] String Graph Assembler(SGA)[10] 및 [11]OULER-SR과 같은 현재 사용 가능한 어셈블러는 SCS [2]어셈블리를 처리하도록 설계되지 않았습니다.단일 셀 데이터의 조립은 균일하지 않은 판독 범위, 삽입 길이의 변화, 높은 수준의 시퀀싱 오류 및 [8][12][13]키메라 판독으로 인해 어렵습니다.따라서 새로운 알고리즘어프로치 SPAdes는 이러한 문제에 대처하기 위해 설계되었습니다.

SPAdes 어셈블리의 어프로치

SPAdes는 초기 de Bruijn 그래프를 구축하기 위해 k-mer를 사용하며, 다음 단계에서는 그래프 구조, 커버리지 및 시퀀스 길이에 기초한 그래프 이론 연산을 수행합니다.또한 [2]오류를 반복적으로 조정합니다.SPAdes의 어셈블리 단계는 다음과 같습니다.[2]

  • 스테이지 1: 어셈블리 그래프 구성.SPAdes는 Multisize de Bruijn 그래프(아래 참조)를 채용하고 있습니다.이 그래프는 벌지/거품 및 키메라 판독치를 검출하여 제거합니다.
  • 2단계: k-바이머(k-mer의 쌍) 조정.게놈의 k-mer 사이의 정확한 거리(조립 그래프의 가장자리)가 추정된다.
  • 3단계: 쌍체 어셈블리 그래프 구성.
  • 스테이지 4: 컨티그 건설.SPAdes는 콘티그 출력을 통해 그래프 단순화(백트랙) 후 어셈블리그래프 내의 위치에 판독치를 매핑할 수 있습니다.

SPAdes 어셈블리 세부 사항

대장균 [14]게놈의 단세포 배열 데이터에 대한 로그 커버리지 플롯.

SPAdes는 다음과 [2]같이 싱글셀 데이터의 어셈블리와 관련된 문제를 해결하도록 설계되었습니다.

1. 균일하지 않은 범위SPAdes는 multisize de Bruijn 그래프를 사용하여 k의 다른 값을 사용할 수 있습니다.fragment화를 최소화하기 위해 저커버리지 영역에서는 작은 k 값을 사용하고 반복 붕괴를 줄이기 위해 고커버리지 영역에서는 큰 k 값을 사용하는 것이 권장되고 있습니다(위의 1단계).

2. 페어링 엔드 판독치의 다양한 삽입 크기.SPAdes는 쌍으로 구성된 de Bruijn 그래프의 기본 개념을 사용합니다.그러나 페어링 드 브루인(paired de Bruijn)은 삽입 크기가 고정된 페어링 엔드 판독에서 잘 작동합니다.따라서 SPAdes는 "insert size"를 사용하는 대신 "distance"를 추정합니다.쌍단 판독치의 거리(d)는 판독 길이 L, d = 삽입 크기 – L로 정의된다. k-가산자 조정 접근방식을 사용하여 정확하게 거리를 추정한다.게놈(αβ, d) 중 k-mers 'α'와 'β'로 이루어진 k-바이머.이 접근방식은 쌍-끝 판독치를 k-mer 쌍으로 나누고, k-mer 쌍은 de Bruijn 그래프에서 에지 쌍(쌍)을 정의하도록 변환한다.이러한 쌍대 세트는 k-mer α와 β 사이의 에지 경로 사이의 거리 추정에 관여한다.군집화를 통해 각 군집으로부터 최적의 거리 추정치가 선택됩니다(2단계, 위).쌍을 이룬 de Bruijn 그래프를 작성하기 위해 SPAdes(3단계)에서 직사각형 그래프를 사용한다.사각 그래프 접근방식은 의심스러운 거리를 가진 쌍체 드 브루인 그래프를 구성하기 위해 2012년에[15] 처음 도입되었다.

3. 불룩한 부분, 끝 부분, 키메라읽기의 중간과 끝의 오류로 인해 볼록한 부분과 끝이 발생합니다.키메라 결합은 게놈의 관련 없는 2개의 서브스트링을 결합한다.SPAdes는 그래프 토폴로지, 여기에 포함된 비브런치 패스의 길이 및 커버리지에 근거하여 이러한 정보를 식별합니다.SPAdes는 모든 수정 또는 삭제를 역추적할 수 있도록 데이터 구조를 유지합니다.

SPAdes는 Peng et al(2010)[17]의 이전에 사용된 벌지 제거[16] 접근법과 반복 de Bruijn 그래프 접근법을 수정하고 벌지 보정 및 제거를 의미하는 "벌지 콜리모벌"이라는 새로운 접근방식을 작성한다.벌지 코리모벌 알고리즘은 다음과 같이 요약할 수 있습니다.단순 벌지는 같은 허브를 접속하는2개의 작고 유사한 패스(P와 Q)에 의해 형성됩니다.P가 비브런치 패스(h-path)인 경우 SPAdes는 P의 모든 엣지를 Q의 엣지 투영에 매핑하고 그래프에서 P를 삭제합니다.그 결과 Q의 커버리지가 증가합니다.고정 커버리지 컷오프 벌지 제거를 사용하는 다른 어셈블러와는 달리 SPAdes는 커버리지가 낮은H 패스를 단계적으로 삭제 또는 투영합니다.이는 점진적으로 증가하는 차단 임계값을 사용하고 모든 H 경로를 통해 커버리지(벌지 콜리버 및 키메라 제거의 경우) 또는 길이(팁 제거의 경우)의 증가 순서로 반복함으로써 달성된다.또한 그래프에 새로운 소스/싱크가 도입되지 않도록 SPAdes는 시작 정점과 끝 정점에 적어도2개의 발신 엣지와 잉고 엣지가 있는 경우에만h 패스(키메라 h 패스 제거) 또는 프로젝트(벌지 콜리벌)를 삭제합니다.이를 통해 시퀀스 오류 및 키메라 판독에서 발생하는 낮은 커버리지h 패스를 제거할 수 있지만 반복에서는 제거할 수 없습니다.

SPAdes 파이프라인 및 퍼포먼스

SPAdes는 다음 [1]도구로 구성됩니다.

  • 오류 수정 도구, BayesHammer(Illumina 데이터용) 및 IonHammer(IonTorrent 데이터용)[14]를 읽습니다.기존의 오류 수정에서는 드문 k-mer는 오류로 간주됩니다.동일하지 않은 적용 범위로 인해 SCS에는 적용할 수 없습니다.따라서 BayesHammer는 유사한 k-mer의 [14]다중 중심 뉴클레오티드를 검사하는 확률론적 하위 클러스터링을 사용한다.대장균(E.coli) 단세포 데이터 세트의 경우 BayesHammer는 약 75분에 실행되며 읽기 오류 수정을 위해 최대 10Gb의 RAM이 필요하며 임시 파일을 위해 10Gb의 추가 디스크 공간이 필요하다고 주장되었습니다.
  • SPAdes를 반복하는 짧은 판독 게놈 어셈블리.동일한 데이터 세트의 경우 이 단계는 최대 75분간 실행됩니다.3회의 반복(k=22, 34 및 56)을 사용하는 경우 1단계(위의 SPAdes 조립 방식 참조)를 수행하는 데 최대 40%의 시간이 소요되며, 2단계, 3단계 및 4단계를 완료하는 데 각각 최대 45%, 14%, 1%의 시간이 소요됩니다.또한 어셈블리에 최대 5Gb의 RAM이 필요하며 8Gb의 추가 디스크 공간이 필요합니다.
  • 불일치 수정자(BWA 도구를 사용).이 모듈에는 가장 긴 시간(최대 120분)과 임시 파일용 최대 추가 디스크 공간(최대 21Gb)이 필요합니다.조립된 대장균 단일 세포 데이터 세트의 불일치 보정을 완료하려면 최대 9Gb RAM이 필요합니다.
  • 고다형 이배체 게놈 조립 모듈인 dipSPades.dipSPades는 반복 게놈 영역에서의 haporf 간의 차이를 이용하여 보다 긴 콘티그(contig)를 구축합니다.그 후 컨센서스 컨티그 컨텐트 구축과 하프타입 조립을 실시한다.

어셈블러 비교

한 연구는[18] 단세포 대장균 샘플을 대상으로 여러 게놈 조립체를 비교했다.이러한 어셈블러는 OULER-SR,[11][9] Velvet, SOAPdenovo,[19] Velvet-SC, OULER+ Velvet-SC([16]E+V-SC[20]), IDBA-UD 및 SPAdes입니다.IDBA-UD 및 SPAdes가 [18]가장 뛰어난 성능을 발휘하는 것으로 나타났습니다.SPAdes의 NG50이 가장 컸습니다(어셈블리 [21]크기가 아닌 게놈 크기가 사용되는 것을 제외하고 NG50 통계는 N50과 동일합니다).또한 대장균 기준 [22]게놈을 사용하여 SPAdes는 게놈 중 가장 높은 비율(97%)과 가장 많은 완전 유전자 수(4,324개 [18]중 4,071개)를 조합했다.조립자의 실적은 다음과 같습니다.[18]

  • 콘티그 수:

IDBA-UD < 벨벳> < E+V-SC < SPAdes < OLER - SR < 벨벳 - SC < SOAPdenovo >

  • NG50

SPAdes > IDBA-UD >> E+V-SC > OLER-SR > Velvet > Velvet-SC > SOAPdenovo

  • 최대 컨티그:

IDBA-UD > SPAdes >> EULER-SR > Velvet= E+V-SC > Velvet-SC > SOAPdenovo

  • 매핑된 게놈(%):

SPAdes > IDBA-UD > E+V-SC > Velvet-SC > OILER-SR > SOAPdenovo > Velvet

  • 잘못된 어셈블리 수:

E+V-SC = 벨벳 = 벨벳-SC < SOAPdenovo < IDBA - UD < SPADes > EULER - SR

「 」를 참조해 주세요.

레퍼런스

  1. ^ a b c d http://spades.bioinf.spbau.ru/release3.0.0/manual.html[데드링크]
  2. ^ a b c d e Bankevich A; Nurk S; Antipov D; Gurevich AA; Dvorkin M; Kulikov AS; Lesin VM; Nikolenko SI; Pham S; Prjibelski AD; Pyshkin AV; Sirotkin AV; Vyahhi N; Tesler G; Alekseyev MA; Pevzner PA. (2012). "SPAdes: a new genome assembly algorithm and its applications to single-cell sequencing". Journal of Computational Biology. 19 (5): 455–477. doi:10.1089/cmb.2012.0021. PMC 3342519. PMID 22506599.
  3. ^ 갤럭시 도구 창고
  4. ^ Gill S; Pop M; Deboy R; Eckburg P; Turnbaugh P; Samuel B; Gordon J; Relman D; Fraser-Liggett C; Nelson K (2006). "Metagenomic analysis of the human distal gut microbiome". Science. 312 (5778): 1355–1359. Bibcode:2006Sci...312.1355G. doi:10.1126/science.1124234. PMC 3027896. PMID 16741115.
  5. ^ Li J; Vederas J (2009). "Drug discovery and natural products: end of an era or an endless frontier?" (PDF). Science. 325 (5937): 161–165. Bibcode:2009Sci...325..161L. doi:10.1126/science.1168243. PMID 19589993. S2CID 206517350.
  6. ^ Lu S; Zong C; Fan W; Yang M; Li J; Chapman A; Zhu P; Hu X; Xu L; Yan L; F B; Qiao J; Tang F; Li R; Xie X (2012). "Probing meiotic recombination and aneuploidy of single sperm cells by whole-genome sequencing". Science. 338 (6114): 1627–1630. Bibcode:2012Sci...338.1627L. doi:10.1126/science.1229112. PMC 3590491. PMID 23258895.
  7. ^ "One cell is all you need". January 4, 2013.
  8. ^ a b Rodrigue S; Malmstrom RR; Berlin AM; Birren BW; Henn MR; Chisholm SW (2009). "Whole genome amplification and de novo assembly of single bacterial cells". PLOS ONE. 4 (9): e6864. Bibcode:2009PLoSO...4.6864R. doi:10.1371/journal.pone.0006864. PMC 2731171. PMID 19724646.
  9. ^ a b Zerbino D; Birney E (2008). "Velvet: algorithms for de novo short read assembly using de Bruijn graphs". Genome Research. 18 (5): 821–829. doi:10.1101/gr.074492.107. PMC 2336801. PMID 18349386.
  10. ^ Simpson JT; Durbin R (2012). "Efficient de novo assembly of large genomes using compressed data structures". Genome Research. 22 (3): 549–556. doi:10.1101/gr.126953.111. PMC 3290790. PMID 22156294.
  11. ^ a b Pevzner PA; Tang H; Waterman MS (2001). "An Eulerian path approach to DNA fragment assembly". Proceedings of the National Academy of Sciences of the United States of America. 98 (17): 9748–9753. Bibcode:2001PNAS...98.9748P. doi:10.1073/pnas.171285098. PMC 55524. PMID 11504945.
  12. ^ Medvedev P; Scott E; Kakaradov B; Pevzner P (2011). "Error correction of high-throughput sequencing datasets with non-uniform coverage". Bioinformatics. 27 (13): i137–141. doi:10.1093/bioinformatics/btr208. PMC 3117386. PMID 21685062.
  13. ^ Ishoey T; Woyke T; Stepanauskas R; Novotny M; Lasken RS (2008). "Genomic sequencing of single microbial cells from environmental samples". Current Opinion in Microbiology. 11 (3): 198–204. doi:10.1016/j.mib.2008.05.006. PMC 3635501. PMID 18550420.
  14. ^ a b c Nikolenko SI; Korobeynikov AI; Alekseyev MA. (2012). "BayesHammer: Bayesian clustering for error correction in single-cell sequencing". BMC Genomics. 14 (Suppl 1): S7. arXiv:1211.2756. doi:10.1186/1471-2164-14-S1-S7. PMC 3549815. PMID 23368723.
  15. ^ Vyahhi N; Pham SK; Pevzner P (2012). From de Bruijn graphs to rectangle graphs for genome assembly. Lecture Notes in Bioinformatics. Lecture Notes in Computer Science. Vol. 7534. pp. 249–261. doi:10.1007/978-3-642-33122-0_20. ISBN 978-3-642-33121-3.
  16. ^ a b Chitsaz H; Yee-Greenbaum JL; Tesler G; Lombardo MJ; Dupont CL; Badger JH; Novotny M; Rusch DB; Fraser LJ; Gormley NA; Schulz-Trieglaff O; Smith GP; Evers DJ; Pevzner PA; Lasken RS (2011). "Efficient de novo assembly of single-cell bacterial genomes from short-read data sets". Nat Biotechnol. 29 (10): 915–921. doi:10.1038/nbt.1966. PMC 3558281. PMID 21926975.
  17. ^ Peng Y.; Leung H.C.M.; Yiu S.-M; Chin FYL (2010). IDBA—a practical iterative de Bruijn graph de novo assembler. Lect. Notes Comput. Sci. Lecture Notes in Computer Science. Vol. 6044. pp. 426–440. Bibcode:2010LNCS.6044..426P. CiteSeerX 10.1.1.157.195. doi:10.1007/978-3-642-12683-3_28. hdl:10722/129571. ISBN 978-3-642-12682-6.
  18. ^ a b c d Gurevich A; Saveliev V; Vyahhi N; Tesler G (2013). "QUAST: quality assessment tool for genome assemblies". Bioinformatics. 29 (8): 1072–1075. doi:10.1093/bioinformatics/btt086. PMC 3624806. PMID 23422339.
  19. ^ Li R; Zhu H; Ruan J; Qian W; Fang X; Shi Z; Li Y; Li S; Shan G; Kristiansen K; Li S; Yang H; Wang J; Wang J (2010). "De novo assembly of human genomes with massively parallel short read sequencing" (PDF). Genome Research. 20 (2): 265–272. doi:10.1101/gr.097261.109. PMC 2813482. PMID 20019144.
  20. ^ Peng Y; Leung HCM; Yiu SM; Chin FYL (2012). "IDBA-UD: a de novo assembler for single-cell and metagenomic sequencing data with highly uneven depth". Bioinformatics. 28 (11): 1–8. doi:10.1093/bioinformatics/bts174. PMID 22495754.
  21. ^ "SPAdes Genome Assembler Algorithmic Biology Lab".
  22. ^ Blattner FR; Plunkett G; Bloch C; Perna N; Burland V; Riley M; Collado-Vides J; Glasner J; Rode C; Mayhew G; Gregor J; Davis N; Kirkpatrick H; Goeden M; Rose D; Mau B; Shao Y (1997). "The complete genome sequence of Escherichia coli K-12". Science. 277 (5331): 1453–1462. doi:10.1126/science.277.5331.1453. PMID 9278503.