벨벳 조립기
Velvet assembler| 개발자 | 다니엘 제르비노,[1] 이완 비르니 |
|---|---|
| 초기 릴리즈 | 2008 |
| 안정적 해제 | 1.2.10 |
| 운영 체제 | 유닉스 유사 |
| 다음에서 사용 가능 | C |
| 유형 | 생물정보학 |
| 면허증 | GPL |
| 웹사이트 | www.ebi.ac.uk/ |
벨벳은 노보 게놈 조립과 짧은 읽기 순서 정렬을 다루기 위해 고안된 알고리즘 패키지다.이는 유전자 시퀀스 조립을 위한 de Bruijn 그래프의 조작을 통해 오류 제거 및 반복 영역 단순화를 통해 달성된다.[2]벨벳은 세켄처, 지니어스, 맥벡터, 바이오Numerics 등 상용 패키지에도 구현됐다.
소개
차세대 시퀀서(NGS)의 개발로 매우 짧은 읽기 시퀀싱에서 비용 효율성이 향상되었다.정렬 방법으로서의 de Bruijn 그래프의 조작은 더욱 현실적이 되었지만 오류와 반복적인 문제를 해결하기 위해서는 추가적인 개발이 필요했다.[3]이는 영국의 유럽 생물정보학 연구소에서 다니엘 제르비노와 이완 비르니의 벨벳 개발로 이어졌다.[4]
벨벳은 그래프 정보의 손실 없이 단순화와 압축을 통해 비절연 경로를 단일 노드로 수렴해 드 브루옌 그래프를 효율적으로 조작하는 방식으로 작동한다.먼저 시퀀스를 병합하는 오류 수정 알고리즘을 사용해 오류를 제거하고 반복을 해결한다.그런 다음 로컬 중첩을 공유하는 경로를 구분하는 반복 해결기를 통해 반복이 시퀀스에서 제거된다.
짧은 읽기-읽기 쌍의 조합으로 벨벳은 작은 반복을 해결하고 적당한 길이의 콘티그를 제작할 수 있다.이번 벨벳 적용은 쌍체 원핵생물 데이터에서 N50 길이 50kb, 포유류 데이터 영역에서는 길이 3kb의 콘티그를 생산할 수 있다.
알고리즘.
이미 언급했듯이, 벨벳은 짧은 읽기를 조립하기 위해 드 브루옌 그래프를 사용한다.좀 더 구체적으로 벨벳은 그래프의 고유 노드가 읽은 것을 통해 얻은 각각의 다른 k-mer를 나타낸다.k-mer가 k-1과 겹칠 경우 두 개의 노드가 연결된다.즉, A로 대표되는 k-mer의 마지막 k-1 문자가 B로 대표되는 k-mer의 첫 번째 k-1 문자일 경우 노드 A에서 노드 B까지의 호가 존재한다.다음 그림은 벨벳으로 생성된 드 브루옌 그래프의 예를 보여준다.
동일한 프로세스가 모든 k-mer의 역보완으로 동시에 이루어지며, 반대쪽 가닥의 읽기 간 중첩을 고려한다.단순화 및 오류 제거를 포함한 여러 가지 최적화를 그래프를 통해 수행할 수 있다.
단순화
메모리 비용을 절감할 수 있는 쉬운 방법은 그래프에서 생성된 경로에 영향을 주지 않는 노드를 병합하는 것이다. 즉, 노드 A가 노드 B를 가리키는 하나의 나가는 호만 가지고 있을 때마다 하나의 진행 중인 호만 있으면 노드를 병합할 수 있다.두 노드를 하나로 표시하여 노드와 노드의 모든 정보를 병합하는 것이 가능하다.다음 그림은 초기 사례의 단순화에서 이 과정을 보여준다.
오류제거
그래프의 오류는 시퀀싱 프로세스에 의해 발생하거나 생물학적 샘플이 일부 오류(예: 다형성)를 포함하는 것일 수 있다.벨벳은 팁, 거품, 잘못된 연결의 세 가지 오류를 인식한다.
팁들
노드는 팁으로 간주되며, 한쪽 끝에서 연결이 끊어지면 지워야 하며, 노드에 저장된 정보의 길이가 2k보다 짧으며, 이 노드로 이어지는 호는 다중성이 낮으며(그래프를 구성하는 동안 호가 발견된 횟수) 그 결과 다른 대체 경로와 비교할 수 없다.일단 이러한 오류가 제거되면, 그래프는 다시 한번 단순화된다.
버블
버블은 두 개의 뚜렷한 경로가 동일한 노드에서 시작하고 끝날 때 생성된다.일반적으로 거품은 오류나 생물학적 변형에 의해 발생한다.이러한 오류는 디즈크스트라의 알고리즘과 유사한 Tour Bus 알고리즘을 사용하여 제거되며, 이는 가장 잘 따르는 경로를 감지하고 어떤 경로를 지워야 하는지를 결정하는 폭 우선 검색이다.간단한 예는 그림 4에 나와 있다.
이 과정은 또한 그림 1과 2에 표시된 예에서 다음 그림 5에 나타나 있다.
잘못된 연결
이들은 올바른 경로를 생성하지 않거나 그래프 내에서 인식 가능한 구조를 생성하지 않는 연결이다.벨벳은 투어버스 알고리즘 완료 후 이러한 오류를 지워 사용자가 정의해야 하는 간단한 커버리지 컷오프를 적용한다.
벨벳 명령
벨벳은 다음과 같은 기능을 제공한다.
- 벨벳의
- 이 명령은 벨벳에 대한 데이터 세트(읽기)를 구성하는 데 도움을 주며 각 시퀀스 파일의 의미에 대한 정보를 포함한다.
- 벨벳처럼 울퉁불퉁한
- 이 명령은 벨벳트가 획득한 k-mer에서 de Bruijn 그래프를 작성하고 그래프 위에 단순화 및 오류 수정을 실행한다.그런 다음 콘티그를 추출한다.
벨벳을 실행한 후에 많은 파일이 생성된다.가장 중요한 것은 콘티그 파일에는 2k보다 긴 콘티그들의 시퀀스가 들어 있는데 여기서 k는 벨벳에서 사용되는 단어 길이다.
자세한 내용 및 예는 Velvet Manual을 참조하십시오.
동기
NGS를 포함한 현재의 DNA 염기서열 기술은 게놈들이 어떤 판독 길이보다 훨씬 크다는 것에 기초하여 제한되어 있다.일반적으로 NGS는 400bp 미만의 작은 판독치로 작동하며, 이전의 1세대 기계에 비해 읽기당 비용이 훨씬 저렴하다.또한 더 높은 병렬 작동과 더 높은 수율을 사용하여 작동하기가 더 간단하다.[3]
그러나 짧은 읽기는 큰 읽기보다 적은 정보를 포함하므로 감지 가능한 중복이 가능하도록 더 높은 어셈블리 읽기 범위를 요구한다.이는 차례로 시퀀싱의 복잡성을 증가시키고 계산 요건을 크게 증가시킨다.판독 횟수가 많을수록 중복 그래프의 크기도 늘어나 계산이 더 어렵고 길다.겹치는 부분의 감소로 인해 오류 발생 가능성이 더 커짐에 따라 읽기 간의 연결부가 더욱 분명하지 않게 된다.
이러한 문제를 극복하기 위해 효율적이고 비용 효율적이며 오류와 반복을 해결할 수 있는 동적 시퀀싱 프로그램이 개발되었다.벨벳 알고리즘은 이를 위해 설계되었으며, 다른 조립자에 비해 메모리 사용량이 적고 비교적 짧은 계산 시간에 짧은 읽기 de novo 시퀀싱 정렬을 수행할 수 있다.[6]
그래픽 인터페이스
벨벳 사용의 주요 단점 중 하나는 커맨드 라인 인터페이스의 사용과 사용자, 특히 초보자가 데이터 구현에서 직면하는 어려움이다.2012년 벨벳 조립자를 위한 그래픽 사용자 인터페이스가 개발되어 이 문제를 극복하고 벨벳의 실행을 단순화하도록 설계되었다.[7]
참고 항목
참조
- ^ Zerbino, D. R. (2010). "Using the Velvetde novo Assembler for Short-Read Sequencing Technologies". In Andreas D. Baxevanis (ed.). Using the Velvet de novo assembler for short-read sequencing technologies. Current Protocols in Bioinformatics. Vol. 31. pp. Unit 11.5. doi:10.1002/0471250953.bi1105s31. ISBN 978-0471250951. PMC 2952100. PMID 20836074.
- ^ 제르비노, D. R.; 버니, E. (2008)"Velvet: 매우 짧은 읽기를 사용하는 노보 어셈블리"2013년 10월 18일 검색됨
- ^ a b Miller, J. R.; Koren, S; Sutton, G (2010). "Assembly algorithms for next-generation sequencing data". Genomics. 95 (6): 315–27. doi:10.1016/j.ygeno.2010.03.001. PMC 2874646. PMID 20211242.
- ^ Zerbino, D. R.; 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.
- ^ 2013년 10월 18일 "Velvet Manual" 검색
- ^ Zhang, W.; Chen, J.; Yang, Y.; Tang, Y.; Shang, J.; Shen, B. (2011). "A Practical Comparison of De Novo Genome Assembly Software Tools for Next-Generation Sequencing Technologies". PLOS ONE. 6 (3): e17915. Bibcode:2011PLoSO...617915Z. doi:10.1371/journal.pone.0017915. PMC 3056720. PMID 21423806.
- ^ Powell, D. R.; Seemann, T (2013). "VAGUE: A graphical user interface for the Velvet assembler". Bioinformatics. 29 (2): 264–5. doi:10.1093/bioinformatics/bts664. PMID 23162059.
