De novo 시퀀스 어셈블러

De novo sequence assemblers

de novo sequence assembler는 참조 게놈을 사용하지 않고 짧은 뉴클레오티드 염기서열을 더 긴 염기서열로 조립하는 프로그램입니다.이것들은 게놈이나 트랜스크립텀을 조립하기 위해 생물정보학 연구에서 가장 일반적으로 사용된다.de novo 어셈블러의 두 가지 일반적인 유형은 탐욕 알고리즘 어셈블러와 De Bruijn 그래프 어셈블러입니다.

de novo 어셈블러의 종류

이러한 어셈블러에 의해 일반적으로 사용되는 알고리즘에는 로컬 최적화를 목적으로 하는 Gready 알고리즘과 글로벌 최적화를 목적으로 하는 Graph 메서드 알고리즘이 있습니다.(작은) 박테리아 게놈, (큰) 진핵생물 게놈 또는 트랜스크립텀의 조립과 같이 다양한 조립자가 특정 요구에 맞게 조정됩니다.

그리디 알고리즘 어셈블러는 작은 판독치 정렬에서 로컬 최적치를 찾는 어셈블리입니다.탐욕 알고리즘 어셈블러는 일반적으로 1) 읽기의 쌍별 거리 계산, 2) 겹치는 부분이 가장 큰 읽기의 클러스터링, 3) 겹치는 읽기의 더 큰 콘티그로의 어셈블리, 4) 반복 등 여러 단계를 특징으로 합니다.이러한 알고리즘은 어셈블리에서 글로벌 최적화에 쉽게 도달할 수 없고 반복 [1]영역을 포함하는 읽기 세트에서는 잘 작동하지 않기 때문에 일반적으로 더 큰 읽기 세트에서는 잘 작동하지 않습니다.SEQAID[2](1984) 및 CAP[3](1992)와 같은 초기 de novo 시퀀스 어셈블러는 OLC(오버랩 레이아웃 컨센서스) 알고리즘과 같은 그리디 알고리즘을 사용했다.이러한 알고리즘은 모든 읽기 간에 오버랩을 찾아내고 오버랩을 사용하여 판독치의 레이아웃(또는 타일링)을 결정한 다음 합의 시퀀스를 생성합니다.OLC 알고리즘을 사용한 일부 프로그램에서는 필터(중복되지 않는 읽기 쌍을 제거하는 것)와 분석 속도를 높이는 경험적 방법을 사용했습니다.

그래프 방식 어셈블러는[4] 문자열과 De Bruijn 두 가지 종류가 있습니다.문자열 그래프와 De Bruijn 그래프 방식 어셈블러는 1994년 DIMACS[5] 워크숍에서 Waterman과 Gene Myers에 [7]의해[6] 소개되었습니다.이들 방법은 모두 로컬 최적값이 아닌 글로벌 최적값에 도달하기 위한 알고리즘을 사용하기 때문에 시퀀스 어셈블리에서 중요한 진전을 보였다.두 방법 모두 더 나은 조립을 위해 발전했지만 De Bruijn 그래프 방법은 차세대 시퀀싱 시대에 가장 인기 있게 되었다.De Bruijn 그래프를 조립하는 동안 판독치는 지정된 크기 k의 작은 조각으로 분할됩니다.그런 다음 k-mer는 그래프 어셈블리의 노드로 사용됩니다.어느 정도 중복되는 노드(일반적으로 k-1)는 에지로 연결됩니다.그런 다음 어셈블러는 De Bruijn 그래프를 기반으로 시퀀스를 작성합니다.De Bruijn 그래프 어셈블러는 일반적으로 그리디 알고리즘 어셈블러보다 큰 읽기 세트에서 더 나은 성능을 발휘합니다(특히 반복 영역을 포함하는 경우).

자주 사용하는 프로그램

신노보 조립자 목록
이름. 설명 /

방법론

 테크놀로지 작가. 표시/

최종 갱신일

 라이선스* 홈페이지
ABYSS 짧은 판독(게놈 및 전사체)의 대규모 게놈 조립을 위해 설계된 병렬, 페어 엔드 시퀀스 어셈블러로 De Bruijn 그래프에 Bloom 필터를 사용한다. 일루미나 [8][9] 2009 / 2017 OS 링크
디스크 페어링 엔드 PCR 프리 읽기(ALLPATHS-LG 후계자) Illumina(MiSeq 또는 HiSeq 2500) [10] 2014 OS 링크
DNA 베이저 배열 어셈블러 자동 엔드 트리밍 및 모호성 보정을 통한 DNA 시퀀스 어셈블리.베이스 발신자를 포함합니다. 일루미나 주 생거 헤라클 바이오 소프트 SRL 2018.09 C(69달러) NA
DNASTAR 라세르겐 유전체 (대) 게놈, 엑소좀, 트랜스콤, 메타제놈, EST Illumina, ABI SOLiD, Roche 454, 이온 토렌트, Solexa, Sanger DNASTAR 2007 / 2016 C 링크
뉴블러 게놈, EST 454, 생어 454 생명과학 2004/2012 C 링크
프랩 게놈 Sanger, 454, Sollexa 녹색, P. 1994 / 2008 C/NC-A 링크
플라스틱 단백질 레벨 어셈블러: 6프레임 변환 시퀀싱 판독치를 단백질 시퀀스로 조립 일루미나 [11] 2018 / 2019 OS 링크
광선 de novo, 메타게노믹, 온톨로지 및 분류학적 프로파일링을 포함한 조립자 스위트; De Bruijn 그래프를 사용한다. [12] 2010 OS 링크
SPAdes (작은) 게놈, 단세포 Illumina, Solexa, Sanger, 454, Ion Torrent, PacBio, Oxford 나노포어 [13] 2012 / 2021 OS 링크
벨벳 (작은) Sanger, 454세, SOLiD, Sollexa [14] 2007 / 2011 OS 링크
HGAP 게놈 최대 130 MB PacBio 읽기 [15] 2011 / 2015 OS 링크
팔콘 이배체 게놈 PacBio 읽기 [16] 2014 / 2017 OS 링크
카누 작고 큰 반배체/이배체 게놈 PacBio/Oxford 나노포어 읽기 [17] 2001 / 2018 OS 링크
MaSuRCA 임의의 크기, 반수체/이배체 게놈 Illumina 및 PacBio/Oxford Nanopore 데이터, 레거시 454 및 Sanger 데이터 [18] 2011 / 2018 OS 링크
힌지 작은 미생물 게놈 PacBio/Oxford 나노포어 읽기 [19] 2016 / 2018 OS 링크
삼위일체 de Bruijn 그래프에 의한 트랜스크립트옴 일루미나 RNA-seq [20] 2011 링크
* 라이선스:OS = 오픈소스, C = Commercial, C / NC-A = Commercial 단, 비상업 및 학계에서는 무료

다양한 유형의 읽기 기술을 위해 다양한 어셈블러가 설계되어 있습니다.Illumina와 같은 2세대 테크놀로지(단독 테크놀로지라고 불린다)로부터의 판독은 일반적으로 짧으며(50~200개의 베이스 페어의 길이), 약 0.5~2%의 에러율을 가지고 있습니다.이 에러는 주로 대체 에러입니다.그러나 PacBio와 같은 제3세대 테크놀로지나 Oxford Nanopore(롱 리드 테크놀로지라고 불린다)와 같은 제4세대 테크놀로지로부터의 판독은 일반적으로 읽기 길이가 수천에서 수만 개로 길며, 주로 삽입과 삭제가 오류 발생률이 10~20%로 훨씬 높습니다.이를 위해서는 짧은 읽기 기술과 긴 읽기 기술과 다른 알고리즘이 필요합니다.

어셈블라톤

de novo sequence assembly에는 수많은 프로그램이 있으며 어셈블리 마라톤에서는 많은 프로그램이 비교되고 있습니다.어셈블라톤은 이용 가능한 수많은 어셈블러를 테스트하고 개선하기 위한 정기적인 공동 작업입니다.현재까지 두 번의 조립이 완료되었고(2011년과 2013년), 세 번째 조립이 진행 중입니다(2017년 4월 현재).전 세계 연구팀이 프로그램을 선택해 시뮬레이션 게놈(어셈블라톤 1)과 이전에 조립해 주석을 달았던 모델 유기체의 게놈(어셈블라톤 2)을 조립한다.그런 다음 여러 메트릭을 사용하여 어셈블리를 비교하고 평가합니다.

어셈블리 마라톤 1

어셈블라톤[21] 1은 2011년에 실시되어 17개의 다른 단체와 주최측에서 59개의 어셈블리가 참가했습니다.이번 어셈블리의 목표는 Evolver를 이용해 생성된 2개의 하플로타입(각각 76.3, 18.5, 17.7Mb의 염색체 3개)으로 구성된 게놈을 가장 정확하고 완전하게 조립하는 것이었다.조립품 평가에는 NG50(가장 긴 발판에서 가장 짧은 발판 길이를 합산할 때 전체 게놈 크기의 50%에 도달하는 지점), LG50(N50 길이보다 크거나 같은 발판 수), 게놈 커버리지 및 치환 오류율을 포함한 수많은 지표가 사용되었습니다.

  • 소프트웨어 비교: ABySS, Pusion2, phrap, Velvet, SOAPdenovo, PRICE, ALLPATHS-LG
  • N50 분석: Plant Genome Assembly Group(조립자 Meraculous 사용)과 ALLPATHS, Broad Institute, USA의 ALLPATHS(ALLPATHS-LG 사용)에 의한 어셈블리는 다른 그룹에 비해 이 범주에서 가장 우수한 성능을 보였다.이들 어셈블리는 8,000,000개 이상의 N50을 획득했습니다.
  • 어셈블리별 게놈 커버리지: 이 메트릭에서는 SOAPdenovo를 통한 BGI 어셈블리가 가장 잘 수행되어 전체 게놈의 98.8%가 커버되었습니다.이 카테고리에서 모든 어셈블러는 비교적 양호한 성능을 보여 3개 그룹을 제외한 모든 그룹이 90% 이상의 커버리지를 가지고 있으며, 가장 낮은 총 커버리지는 78.5%(컴포트의 부서)입니다.Ci., 미국 시카고 대학교 Kiki 경유).
  • 대체 오류: 교체 오류율이 가장 낮은 어셈블리는 영국 Wellcome Trust Sanger Institute에서 소프트웨어 SGA를 사용하여 제출했습니다.
  • 전체:모든 카테고리에서 다른 어셈블러보다 월등히 뛰어난 성능을 발휘한 어셈블러는 없었습니다.일부 어셈블러는 한 카테고리에서 우수했지만 다른 카테고리에서는 우수하지 않았기 때문에 어셈블러 소프트웨어의 품질은 여전히 개선될 여지가 있음을 알 수 있습니다.

어셈블리 마라톤 2

어셈블라톤2는[22] 길이가 1.2, 1.0, 1.6Gbp로 추정되는 다배체 척추동물(새(Melopsittacus undulatus), 어류(Maylandia zebra), 뱀(Boa crestrictor)의 게놈을 배합해 100개 이상의 메트릭으로 평가함으로써 어셈블리라톤1을 개선했다.각 팀은 일루미나와 로체 454 염기서열 데이터를 포함한 차세대 염기서열(NGS) 데이터에서 게놈을 조립하는 데 4개월이 주어졌다.

  • 소프트웨어 비교: ABySS, ALLPATHS-LG, PRICE, Ray 및 SOAPdenovo
  • N50 분석: 조류 게놈 조립에서는 베일러 의과대학 인간 게놈 시퀀싱 센터와 ALLPATHS 팀이 각각 1,600만 bp 이상, 1,400만 bp 이상으로 NG50이 가장 높았다.
  • 핵심 유전자의 존재:대부분의 어셈블리는 이 범주에서 양호한 성능을 보였으며(80% 이상), 조류 게놈 어셈블리에서 단 1개만 50%로 떨어졌습니다(HyDA를 통한 웨인 주립 대학).
  • 전체:전반적으로 다양한 조립 방법(SeqPrep, KmerFreq, Quake, BWA, Newbler, ALLPATHS-LG, Atlas-Link, Atlas-GapFill, Phrap, CrossMatch, Velvet, BLAS)을 활용하는 베일러 의과대학 인간 게놈 배열 분석 센터뱀 게놈 조립은 SGA를 이용한 웰컴 트러스트 생어 연구소가 가장 잘했다.모든 어셈블리에 대해 SGA, BCM, Meraculous 및 Ray가 경쟁 어셈블리 및 평가를 제출했습니다.여기에 설명된 많은 어셈블리와 평가의 결과에 따르면 한 어셈블러는 한 종에서는 잘 수행되지만 다른 종에서는 잘 수행되지 않을 수 있습니다.저자들은 조립에 대해 여러 가지 제안을 한다. 1) 하나 이상의 조립체를 사용하고 2) 평가를 위해 하나 이상의 메트릭을 사용하고 3) 더 관심 있는 메트릭(예: N50, 적용 범위), 4) 낮은 N50 또는 조립체 크기는 사용자의 요구에 따라 상관 없을 수 있으며, 5) 게놈에서 이형 접합체의 수준을 평가할 수 있다.f interest.

「 」를 참조해 주세요.

레퍼런스

  1. ^ J. Bang-Jensen; G. Gutin; A. Yeo (2004). "When the greedy algorithm fails". Discrete Optimization. 1 (2): 121–127. doi:10.1016/j.disopt.2004.03.007.
  2. ^ Peltola, Hannu; Söderlund, Hans; Ukkonen, Esko (1984-01-11). "SEQAID: a DNA sequence assembling program based on a mathematical model". Nucleic Acids Research. 12 (1Part1): 307–321. doi:10.1093/nar/12.1Part1.307. ISSN 0305-1048. PMC 321006. PMID 6320092.
  3. ^ Huang, Xiaoqiu (1992-09-01). "A contig assembly program based on sensitive detection of fragment overlaps". Genomics. 14 (1): 18–25. doi:10.1016/S0888-7543(05)80277-0. PMID 1427824.
  4. ^ Compeau, Phillip EC, Pavel A. Pevzner, and Glenn Tesler (2011). "How to apply de Bruijn graphs to genome assembly". Nature Biotechnology. 29 (11): 987–991. doi:10.1038/nbt.2023. PMC 5531759. PMID 22068540.{{cite journal}}: CS1 maint: 작성자 파라미터 사용(링크)
  5. ^ "DIMACS Workshop on Combinatorial Methods for DNA Mapping and Sequencing". October 1994.
  6. ^ Idury, R. M.; Waterman, M. S. (1995-01-01). "A new algorithm for DNA sequence assembly". Journal of Computational Biology. 2 (2): 291–306. CiteSeerX 10.1.1.79.6459. doi:10.1089/cmb.1995.2.291. ISSN 1066-5277. PMID 7497130.
  7. ^ Myers, E. W. (1995-01-01). "Toward simplifying and accurately formulating fragment assembly". Journal of Computational Biology. 2 (2): 275–290. doi:10.1089/cmb.1995.2.275. ISSN 1066-5277. PMID 7497129.
  8. ^ Simpson, Jared T.; et al. (2009). "ABySS: a parallel assembler for short read sequence data". Genome Research. 19 (6): 1117–1123. doi:10.1101/gr.089532.108. PMC 2694472. PMID 19251739.
  9. ^ Birol, Inanç; et al. (2009). "De novo transcriptome assembly with ABySS". Bioinformatics. 25 (21): 2872–2877. doi:10.1093/bioinformatics/btp367. PMID 19528083.
  10. ^ Love, R. Rebecca; Weisenfeld, Neil I.; Jaffe, David B.; Besansky, Nora J.; Neafsey, Daniel E. (December 2016). "Evaluation of DISCOVAR de novo using a mosquito sample for cost-effective short-read genome assembly". BMC Genomics. 17 (1): 187. doi:10.1186/s12864-016-2531-7. ISSN 1471-2164. PMC 4779211. PMID 26944054.
  11. ^ Steinegger, Martin; Mirdita, Milot; Söding, Johannes (2019-06-24). "Protein-level assembly increases protein sequence recovery from metagenomic samples manyfold". Nature Methods. 16 (7): 603–606. doi:10.1038/s41592-019-0437-4. hdl:21.11116/0000-0003-E0DD-7. PMID 31235882.
  12. ^ Boisvert, Sébastien, François Laviolette, and Jacques Corbeil (2010). "Ray: simultaneous assembly of reads from a mix of high-throughput sequencing technologies". Journal of Computational Biology. 17 (11): 1519–1533. doi:10.1089/cmb.2009.0238. PMC 3119603. PMID 20958248.{{cite journal}}: CS1 maint: 작성자 파라미터 사용(링크)
  13. ^ Bankevich, Anton; Nurk, Sergey; Antipov, Dmitry; Gurevich, Alexey A.; Dvorkin, Mikhail; Kulikov, Alexander S.; Lesin, Valery M.; Nikolenko, Sergey I.; Pham, Son; Prjibelski, Andrey D.; Pyshkin, Alexey V. (May 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. ISSN 1066-5277. PMC 3342519. PMID 22506599.
  14. ^ Zerbino, D. R.; Birney, E. (2008-02-21). "Velvet: Algorithms for de novo short read assembly using de Bruijn graphs". Genome Research. 18 (5): 821–829. doi:10.1101/gr.074492.107. ISSN 1088-9051. PMC 2336801. PMID 18349386.
  15. ^ 친, 천산, 데이비드 H. 알렉산더, 패트릭 마크스, 애런 A.클라머, 제임스 드레이크, 셰릴 하이너, 앨리샤 클룸 등"오랜 시간 동안 읽혀진 SMRT 염기서열 분석 데이터로부터 완성된 미생물 게놈 조립체입니다."자연방법 10, No. 6 (2013) : 563-569.온라인으로 이용 가능
  16. ^ 친, 첸산, 폴 펠루소, 프리츠 J. 세들라섹, 마리아 나트스타드, 그레고리 T.콘셉시온, 앨리샤 클럼, 크리스토퍼 던 등"단분자 실시간 염기서열 분석을 통한 단계적 이중배체 게놈 조립"자연방법 13, No. 12 (2016) : 1050-1054.이쪽에서 입수 가능
  17. ^ 코렌, 세르게이, 브라이언 P.발렌츠, 콘스탄틴 베를린, 제이슨 R.밀러, 니콜라스 H. 버그먼, 아담 M.필리피."Canu: 적응형 k-mer 무게 부여 및 반복 분리를 통해 확장 가능하고 정확한 읽기 어셈블리입니다."게놈 연구 27, No. 5 (2017) : 722-736.이쪽에서 입수 가능
  18. ^ Zimin, Aleksey V.; Marçais, Guillaume; Puiu, Daniela; Roberts, Michael; Salzberg, Steven L.; Yorke, James A. (November 2013). "The MaSuRCA genome assembler". Bioinformatics. 29 (21): 2669–2677. doi:10.1093/bioinformatics/btt476. ISSN 1367-4803. PMC 3799473. PMID 23990416.
  19. ^ 카마스, 고빈다 M., 일란 쇼모로니, 페이샤, 토마스 A.Courtade와 N.체데이비드."HINGE: 장시간 읽기 어셈블리는 최적의 반복 해상도를 실현합니다."게놈 연구 27, No. 5 (2017) : 747-756.이쪽에서 입수 가능
  20. ^ Grabherr, Manfred G.; et al. (2011). "Full-length transcriptome assembly from RNA-Seq data without a reference genome". Nature Biotechnology. 29 (7): 644–652. doi:10.1038/nbt.1883. PMC 3571712. PMID 21572440.
  21. ^ Earl, Dent; et al. (December 2011). "Assemblathon 1: A competitive assessment of de novo short read assembly methods". Genome Research. 21 (12): 2224–2241. doi:10.1101/gr.126599.111. PMC 3227110.
  22. ^ Bradnam, Keith R.; et al. (2013). "Assemblathon 2: evaluating de novo methods of genome assembly in three vertebrate species". GigaScience. 2 (1): 10. arXiv:1301.5406. doi:10.1186/2047-217X-2-10. PMC 3844414. PMID 23870653.