시퀀스 어셈블리

Sequence assembly

생물정보학에서 배열조립은 원래의 배열을 재구성하기 위해 더 긴 DNA 배열의 조각들을 정렬하고 병합하는 것을 말한다.이는 DNA 염기서열 분석 기술이 한 번에 전체 게놈을 '읽는' 것이 아니라 사용된 기술에 따라 20,000개에서 30,000개의 염기의 작은 조각들을 읽을 수 있기 때문에 필요하다.일반적으로 짧은 단편(판독치)은 산탄총 염기서열 분석 DNA 또는 유전자 전사(EST)에서 비롯됩니다.

시퀀스 어셈블리의 문제는 많은 책을 복사하고, 각각의 책을 다른 커터로 파쇄기에 통과시키고, 파쇄된 조각들을 보는 것만으로 책의 텍스트를 다시 연결하는 것과 비교할 수 있습니다.이 태스크의 명백한 어려움 외에도 몇 가지 현실적인 문제가 있습니다. 원본에는 반복된 단락이 많을 수 있으며, 분쇄 중에 일부 조각이 수정되어 오타가 있을 수 있습니다.다른 책에서 발췌한 내용도 추가될 수 있으며 일부 조각은 완전히 인식되지 않을 수 있습니다.

게놈 어셈블러

최초의 시퀀스 어셈블러는 1980년대 후반과 1990년대 초반에 DNA 시퀀서라고 불리는 자동화된 시퀀스 장치에 의해 생성된 방대한 양의 단편들을 결합하는 단순한 시퀀스 얼라인먼트 프로그램의 변형으로 나타나기 시작했다.배열된 유기체의 크기와 복잡성이 커짐에 따라(플라스미드보다 작은 바이러스에서 박테리아, 그리고 마지막으로 진핵생물까지) 이러한 게놈 프로젝트에 사용되는 조립 프로그램은 다음을 다루기 위한 더욱 정교한 전략이 필요했습니다.

  • 컴퓨팅 클러스터에서의 처리가 필요한 수 테라바이트의 데이터 시퀀싱
  • 최악의 경우 알고리즘의 시간과 공간의 복잡성을 2차적으로 증가시킬 수 있는 동일하고 거의 동일한 시퀀스(반복으로 알려져 있음)
  • 염기서열 분석 기구의 단편에서 DNA 판독 오류가 발생하여 조립을 혼동할 수 있습니다.

2000년에 최초의 더 큰 진핵 genomes—the 과일 파리인 초파리 melanogaster 조립의 도전과 인간 게놈에 직면하면 불과 1년 later,—scientists Celera Assembler[1]과 Arachne[2]1억 3000만(예:은 과일 파리 Dmelanogaster)에게 30억(예:인간 게놈)bas의 게놈을 처리할 능력이 같은 조립을 개발했다.e쌍s. 이러한 노력 후에, 주로 주요 게놈 배열 센터에 있는 몇몇 다른 그룹들이 대규모 어셈블러를 만들었고, AMOS로[3] 알려진 오픈 소스 작업이 시작되어 오픈 소스 프레임워크 하에서 게놈 조립 기술의 모든 혁신을 통합했습니다.

시퀀스 어셈블러가 fragment(검은색 막대 아래 표시)를 취하여 이들 사이에 매치가 겹쳐서 최종 시퀀스(검은색)를 조립하는 방법.잠재적으로 문제가 발생할 수 있는 반복이 시퀀스 위에 표시됩니다(위의 분홍색).중복되는 fragment가 없으면 이러한 세그먼트를 특정 영역에 할당하지 못할 수 있습니다.

EST 어셈블러

발현배열태그 또는 EST조립은 1990년대 중반부터 2000년대 중반까지 거슬러 올라가 전체 게놈이 아닌 개별 유전자를 조립하는 초기 전략이었다.그 문제는 몇 가지 점에서 게놈 조립과 다르다.EST 조립을 위한 입력 시퀀스는 세포의 전사된 mRNA의 단편이며 전체 게놈의 하위 집합만을 나타낸다.게놈과 EST 조립체 사이에 많은 알고리즘 문제가 다르다.예를 들어, 게놈은 종종 유전자간 영역에 집중된 대량의 반복 서열을 가지고 있다.전사된 유전자는 반복 횟수가 훨씬 적기 때문에 조립이 다소 쉬워집니다.한편, 일부 유전자는 매우 높은 수(예를 들어, 하우스키핑 유전자)로 발현(전사)되는데, 이는 전체 유전자 산탄총 염기서열 분석과 달리 게놈 전체에서 판독치가 균일하게 샘플링되지 않는다는 것을 의미한다.

EST 조립은 (cis-) 대체 스플라이싱, 트랜스 스플라이싱, 단일 뉴클레오티드 다형성 및 전사 후 수정과 같은 특징에 의해 훨씬 더 복잡해진다.RNA-Seq가 발명된 2008년부터 EST 시퀀싱은 de novo transcriptome 조립체 하에서 기술된 훨씬 더 효율적인 기술로 대체되었습니다.

시퀀스 어셈블리의 유형

시퀀스 어셈블리의 종류

시퀀싱 데이터를 조합하는 방법에는 다음 세 가지가 있습니다.

  1. De-novo: 템플릿을 사용하지 않고 시퀀스 판독을 조립하여 전체 길이(때로는 새로운) 시퀀스를 만듭니다(de novo 시퀀스 어셈블러, de novo 스크립트 어셈블리 참조).
  2. 매핑/정렬: 템플릿에 대해 판독치를 정렬하여 판독치를 조립합니다(AKA 참조).수집된 컨센서스가 템플릿과 동일하지 않을 수 있습니다.
  3. 참조 가이드: 참조 내에서 가장 유사한 영역과의 유사성에 따라 판독치를 그룹화합니다(단계별 매핑).그 후, 각 그룹내의 판독치는, 짧은 판독 품질의 흉내를 내기 위해서 단축됩니다.이를 위한 일반적인 방법은 k-mer 접근법이다.참조 가이드 어셈블리는 긴 판독치를 사용하는 경우에 가장 유용합니다.

참조 안내 어셈블리는 다른 유형의 조합입니다.이 유형은 짧은 읽기 이점(즉, 통화 품질)을 모방하기 위해 긴 읽기에 적용됩니다.그 이면에 있는 논리는 참조 내의 작은 창별로 읽기를 그룹화하는 것입니다.각 그룹의 판독치는 k-mere 접근방식을 사용하여 크기를 줄이고 최고 품질과 가장 가능성이 높은 연속(계속)을 선택합니다.그리고 콘티그들이 합쳐져 발판을 만들 것이다.최종 합의는 비계의 틈새를 메움으로써 이루어진다.

혁신과매핑 어셈블리

복잡성 및 시간 요구사항 측면에서, de-novo 어셈블리는 매핑 어셈블리보다 훨씬 느리고 메모리 집약적입니다.이것은 주로 어셈블리알고리즘이 모든 판독치를 다른 판독치와 비교할 필요가 있다는 사실에 기인합니다(O의 순진한 시간복잡도를 갖는 연산).n2)) 현재 de-novo 게놈 어셈블러는 다음과 같은 다양한 유형의 그래프 기반 알고리즘을 사용할 수 있습니다.

  • OLC(Overlap/Layout/Consensence) 접근법. OLC는 Sanger 데이터 어셈블러의 전형적인 방식이며 오버랩 그래프에 의존합니다.
  • De Bruijn Graph (DBG) 어프로치는 Solexa 및 SOLiD 플랫폼에서의 짧은 판독에 가장 폭넓게 적용됩니다.K-mer 그래프에 의존하며, 이 그래프는 방대한 양의 짧은 읽기에서도 잘 작동합니다.
  • OLC 또는 DBG 접근 방식 중 하나를 사용할 수도 있는 그리디 그래프 기반 접근 방식입니다.그리디 그래프 기반 알고리즘에서는 콘티그(contig[further explanation needed])가 그리디 확장에 의해 증가하며, 항상 가장 높은 점수 [4]오버랩에 따라 검색된 읽기를 담당합니다.

서론에서 분쇄된 책과 비교한 내용: 지도 어셈블리의 경우 템플릿과 매우 유사한 책이 있을 수 있지만(아마 주인공의 이름이 바뀌어 몇 군데 위치가 바뀌었을 수도 있음), 디노보 어셈블리는 이것이 과학이 될지 미리 알 수 없다는 점에서 더 위압적인 과제를 제기합니다.책, 소설, 카탈로그, 심지어 몇 권의 책도 있다.또한 모든 조각이 다른 조각과 비교될 것입니다.

de-novo 어셈블리에서 반복을 처리하려면 인접 반복을 나타내는 그래프를 구성해야 합니다.이러한 정보는 반복을 모두 포함하거나 양끝만 포함하는 긴 조각을 읽음으로써 얻을 수 있습니다.한편, 매핑 어셈블리에서는, 통상, 복수의 일치 또는 일치하지 않는 부품은,[5] 다른 조립 기법으로 조사하기 위해서 남겨집니다.

시퀀스 어셈블리 파이프라인(생물정보학)

일반적으로 시퀀싱 판독치를 발판에 조립하는 절차는 세 가지가 있습니다.

1) 조립 전: 이 단계는 변종 호출 또는 최종 발판 시퀀스 등 다운라인 분석의 무결성을 보장하기 위해 필수적입니다.이 단계는 2개의 시간순 워크플로우로 구성됩니다.

A) 품질 체크:시퀀싱 테크놀로지의 종류에 따라서는, 다른 에러가 발생해, 잘못된 베이스 콜이 발생하는 일이 있습니다.예를 들어, 12 아데닌을 포함하는 "NAAAAAAAAAAAAN" 및 "NAAAAAAAAAAAAAN" 배열은 11 아데닌으로 잘못 호출될 수 있다.타겟 DNA/RNA 의 고도로 반복적인 세그먼트의 시퀀스를 지정하면, 콜이 1 개 또는 복수의 베이스가 되는 경우가 있습니다.판독 품질은 일반적으로 Pred에 의해 측정되며, Pred는 판독 시퀀스 내의 각 뉴클레오티드 품질에 대한 부호화된 점수이다.PacBio와 같은 일부 시퀀싱 기술에는 시퀀싱된 판독치에 대한 스코어링 방법이 없습니다.이 단계에서 일반적으로 사용되는 도구는 FastQC입니다.[6]

B) 판독치 필터링: 품질 체크에 실패한 판독치는 FastQ 파일에서 삭제하여 최적의 어셈블리 콘티그먼트를 얻을 수 있습니다.

2) 어셈블리: 이 스텝에서는 판독치 정렬을 다른 기준으로 사용하여 각 판독치를 가능한 위치에 매핑합니다.판독치의 예측 위치는 시퀀스의 어느 정도가 다른 판독치 또는 참조와 일치하는지 기준으로 결정됩니다.다른 정렬 알고리즘은 다른 시퀀싱 기술로부터의 판독에 사용됩니다.어셈블리에서 일반적으로 사용되는 접근법으로는 de Bruijn 그래프와 오버랩이 있습니다.차세대 [7]시퀀싱의 경우 최적의 정렬 알고리즘을 선택하는 데는 판독 길이, 커버리지, 품질 및 사용된 시퀀스 처리 기술이 중요한 역할을 합니다.한편, 3세대 시퀀싱 읽기를 정렬하는 알고리즘에서는, 이러한 알고리즘에 관련하는 높은 에러율을 설명하기 위한 고도의 어프로치가 필요합니다.

3) 조립 후:이 단계에서는 조립된 시퀀스에서 중요한 정보를 추출하는 데 초점을 맞춥니다.비교유전체학, 인구분석은 조립 후 분석의 예다.

기술 변화의 영향

시퀀스 어셈블리의 복잡성은 fragment의 수와 길이라는 두 가지 주요 요인에 의해 결정됩니다.점점 더 긴 조각이 시퀀스 오버랩을 더 잘 식별할 수 있게 하지만, 기본 알고리즘이 조각의 수와 길이 모두에 대해 2차 또는 심지어 지수 복잡성 동작을 보여주기 때문에 문제를 야기하기도 한다.짧은 시퀀스는 정렬 속도가 빠르지만 짧은 판독치는 반복 또는 거의 동일한 반복에서 사용하기 어렵기 때문에 어셈블리의 레이아웃 단계도 복잡해집니다.

DNA 염기서열 분석의 초창기에, 과학자들은 몇 주 동안 실험실에서 일한 후에 짧은 길이의 염기서열 몇 개만 얻을 수 있었다.따라서 이러한 시퀀스는 몇 분 안에 수동으로 정렬할 수 있습니다.

1975년에 디데옥시 종단 방법(일명 생어 시퀀스 방식)이 발명되었고, 2000년 직후까지 이 기술은 완전 자동화 기계가 24시간 고도로 병렬화된 모드에서 시퀀스를 생산할 수 있는 수준까지 향상되었습니다.전 세계의 큰 게놈 센터는 이러한 배열 분석 기계의 완전한 농장을 수용했고, 이는 결국 전체 유전자 산탄총 배열 프로젝트의 시퀀스를 위해 조립자가 최적화될 필요성을 가져왔다.

  • 약 800~900개의 베이스 길이
  • 벡터 배열 및 클로닝과 같은 배열 아티팩트를 포함하다
  • 에러율이 0.5~10%이다

Sanger 기술을 사용하면 20,000에서 20,000의 판독치를 가진 박테리아 프로젝트를 컴퓨터 한 대에 쉽게 조립할 수 있습니다.약 3,500만 개의 판독치를 가진 인간 게놈과 같은 대규모 프로젝트에는 대규모 컴퓨팅 팜과 분산 컴퓨팅이 필요했습니다.

2004/2005년에는 454 생명과학에 의해 파이로시퀀싱이 상업적으로 실현되었습니다.생성된 이 새로운 시퀀싱 방법은 Sanger 시퀀싱보다 훨씬 짧습니다.처음에는 약 100베이스, 현재는 400~500베이스입니다.Sanger 시퀀싱에 비해 훨씬 높은 throughput과 낮은 비용 때문에 게놈 센터에서 이 기술을 채택하게 되었고, 결과적으로 읽기 세트를 효율적으로 처리할 수 있는 시퀀스 어셈블러의 개발이 추진되었습니다.방대한 양의 데이터와 읽기 기술 고유의 오류 패턴으로 인해 어셈블러의 개발이 지연되었습니다. 2004년에는 454의 Newbler 어셈블러만 사용할 수 있었습니다.2007년 [8]중반에 출시된 Shevreux 등의 하이브리드 버전의 MIRA 어셈블러는 454개의 판독치 및 454개의 판독치 및 Sanger 판독치의 혼합물을 조립할 수 있는 최초의 무료 어셈블리러였습니다.다른 시퀀싱 기술로부터 시퀀스를 조립하는 것이 그 후에 하이브리드 어셈블리로 만들어졌습니다.

2006년부터는 Illumina(이전의 Solexa) 테크놀로지를 이용할 수 있게 되어, 1회의 시퀀싱 머신으로 1회의 실행당 약 1억개의 판독치를 생성할 수 있게 되었습니다.이것을 인간 게놈 프로젝트의 3,500만 개의 판독치들과 비교해보라. 수백 개의 염기서열 분석 기계로 생산하는데 몇 년이 걸렸다.Illumina는 처음에는 36베이스의 길이로 제한되었기 때문에 de novo 어셈블리(de novo transcriptome 어셈블리 등)에 적합하지 않지만, 새로운 기술의 반복으로 3-400bp 클론의 양 끝에서 100베이스 이상의 읽기 길이가 달성되었습니다.2007년 말에 발표된 Dohm 등의 SHARCGS 어셈블러는[9] Solexa 판독을 사용한 어셈블리에 사용된 최초의 공개 어셈블리입니다.다른 많은 사람들이 그 뒤를 빠르게 따랐다.

이후 Applied Biosystems, Ion Torrent 및 SMRT의 SOLiD와 같은 신기술이 출시되었고 새로운 기술(예: Nanopore Sequencing)이 계속해서 등장하고 있습니다.이러한 테크놀로지의 에러율은 높지만, 읽기 길이가 길면 반복적인 문제에 대처할 수 있기 때문에 조립에 중요합니다.최대 읽기 길이보다 긴 완벽한 반복을 통해 조립하는 것은 불가능하지만, 읽기가 길어질수록 크기가 작아지는 완벽한 반복의 가능성이 높아집니다.따라서 시퀀싱이 길면 정확도가 낮더라도 반복을 조립할 때 유리합니다(~85%).

어셈블리 알고리즘

다른 유기체들은 그들의 게놈 안에서 더 복잡성이 높은 뚜렷한 영역을 가지고 있다.따라서 서로 다른 계산 접근법이 필요하다.일반적으로 사용되는 알고리즘은 다음과 같습니다.

  • 그래프 어셈블리: 컴퓨터 과학의 그래프 이론을 기반으로 합니다.de Bruijn Graph는 이 접근방식의 한 예이며 k-mer를 사용하여 판독에서 연속된 것을 조립합니다.
  • Gready Graph Assembly: 이 접근법은 어셈블리에 읽혀진 각 항목을 채점하고 겹치는 영역에서 가장 높은 점수를 선택합니다.

시퀀스 프래그먼트세트를 지정하면 오브젝트는 모든 fragment를 포함하는 긴 시퀀스를 검색합니다([Types of Sequence Assembly]아래 그림 참조).

  1. § 모든 fragment의 쌍방향 얼라인먼트를 계산한다.
  2. 겹치는 부분이 가장 큰 2개의 fragment
  3. 선택한 fragment를 Marge합니다.
  4. 1개의 fragment만 남을 때까지 스텝2와 3을 반복합니다.

결과가 문제에 대한 최적의 해결책이 아닐 수 있습니다.

프로그램

de-novo 어셈블러 목록은 de-novo 시퀀스 어셈블러를 참조하십시오.매핑 얼라이너 목록은 시퀀스 정렬 소프트웨어 목록 § 짧은 읽기 시퀀스 정렬을 참조하십시오.

다른 어셈블리 단계에서 사용되는 일반적인 도구의 일부를 다음 표에 나타냅니다.

시퀀스 어셈블리 도구
소프트웨어 읽기 유형 도구 웹 페이지 메모들
FastQC 복수 https://www.bioinformatics.babraham.ac.uk/projects/fastqc/ Illumina, 454 및 PacBio와 같은 다양한 시퀀싱 기술에서 판독 품질을 확인하는 데 사용되는 일반적인 도구입니다.
BWA 짧은 읽기 및 긴 읽기 https://sourceforge.net/projects/bio-bwa/files/ 명령줄 도구입니다.대부분 경량 주행과 정확한 시퀀스 정렬로 알려져 있습니다.
미니맵2 긴 읽기 https://github.com/lh3/minimap2 이 명령줄 툴은 PacBio 및 Oxford Nanopore에 대응하도록 설계되어 에러율이 15%입니다.
LoReTTA 긴 읽기 https://github.com/salvocamiolo/LoReTTA/releases/tag/v0.1 이 도구는 PacBio CCS 판독을 사용하여 바이러스 게놈을 보다 정확하게 조립(참조)하도록 설계되었습니다.
SPAdes 짧은 읽기 및 긴 읽기 http://cab.spbu.ru/software/spades/ 명령줄에서 실행되는 어셈블리 도구입니다.
삼도구 정렬 분석 https://samtools.github.io 이것은 편리한 포스트 어셈블리입니다.다른 통계를 생성하고 정렬 파일에 대해 여러 필터링 단계를 수행할 수 있습니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Myers, E. W.; Sutton, GG; Delcher, AL; Dew, IM; Fasulo, DP; Flanigan, MJ; Kravitz, SA; Mobarry, CM; et al. (March 2000). "A whole-genome assembly of Drosophila". Science. 287 (5461): 2196–204. Bibcode:2000Sci...287.2196M. CiteSeerX 10.1.1.79.9822. doi:10.1126/science.287.5461.2196. PMID 10731133. S2CID 6049420.
  2. ^ Batzoglou, S.; Jaffe, DB; Stanley, K; Butler, J; Gnerre, S; Mauceli, E; Berger, B; Mesirov, JP; Lander, ES (January 2002). "ARACHNE: a whole-genome shotgun assembler". Genome Research. 12 (1): 177–89. doi:10.1101/gr.208902. PMC 155255. PMID 11779843.
  3. ^ AMOS 페이지 (각종 논문 링크 포함)
  4. ^ Miller, Jason R.; Koren, Sergey; Sutton, Granger (2010-03-06). "Assembly algorithms for next-generation sequencing data". Genomics. 95 (6): 315–327. doi:10.1016/j.ygeno.2010.03.001. PMC 2874646. PMID 20211242.
  5. ^ Wolf, Beat. "De novo genome assembly versus mapping to a reference genome" (PDF). University of Applied Sciences Western Switzerland. Retrieved 6 April 2019.
  6. ^ "Babraham Bioinformatics - FastQC A Quality Control tool for High Throughput Sequence Data". www.bioinformatics.babraham.ac.uk. Retrieved 2022-05-09.
  7. ^ Ruffalo, M.; LaFramboise, T.; Koyuturk, M. (2011-10-15). "Comparative analysis of algorithms for next-generation sequencing read alignment". Bioinformatics. 27 (20): 2790–2796. doi:10.1093/bioinformatics/btr477. ISSN 1367-4803.
  8. ^ bionet.software Usenet 그룹의 MIRA 2.9.8 하이브리드 버전을 발표하는 게시물의 Google 그룹에 복사
  9. ^ Dohm, J. C.; Lottaz, C.; Borodina, T.; Himmelbauer, H. (November 2007). "SHARCGS, a fast and highly accurate short-read assembly algorithm for de novo genomic sequencing". Genome Research. 17 (11): 1697–706. doi:10.1101/gr.6435207. PMC 2045152. PMID 17908823.