짧은 요약(Abstract) :    
* iBLAST 시스템은 이전 결과를 활용하여 새로운 데이터베이스 시퀀스가 추가될 때 이를 업데이트함으로써 새로운 시퀀스에 대한 효율적인 BLAST 검색을 위해 설계  
* 이 접근 방식은 업데이트된 결과에 대한 중요한 통계, 예를 들어 e-value를 재계산하여 상당한 계산 비용을 절감  
* iBLAST는 최근 NCBI BLAST 도구와 호환되며 BLAST에 익숙한 사용자에게 사용자 친화적  

Useful sentences :  
*


Paper link
Lecture link


단어정리

  • astronomical: 비유적으로 우주만큼 광대하게 거대하게
  • sensitivity: 민감도, 사실상 recall과 같음 TP / (TP + FN)
  • taxa: 하나의 분류 단위
  • taxonomy: 분류체계
  • burden: 부담, 중압감
  • HSP: 이 논문에서는 High Scoring Pairs
  • fidelity: 정확성, 충실도, 신뢰도
  • venom gland: 독샘 - venom:독, gland:샘
  • oak gall wasp: 참나무 흑벌 - wasp: 벌
  • hedgehog: 고슴도치
  • Nasonia vitripennis: 기생말벌
  • apis mellifera: 서양말벌
  • Hymenoptera: 곤충목
  • harpegnathos saltator: 점프 개미
  • drosophilla melanogaster: 초파리
  • quercus suber: 코르크 참나무
  • glycine max: 콩
  • aggravated: 악화된, 더 심각해진


Introduction

  • iBLAST 시스템은 데이터베이스에 새로 추가된 시퀀스를 반영하여 BLAST 검색 결과를 업데이트하는 새롭고 효율적인 방법을 소개
  • 전체 검색을 다시 실행하지 않고도 이를 수행함으로써 계산 자원과 시간을 크게 절약
  • 이 방법은 새로운 시퀀스가 지속적으로 추가되면서 데이터베이스가 빠르게 성장하는 유전학 분야에서 특히 유용
  • 기존의 방식은 업데이트된 데이터베이스에 대해 전체 BLAST 검색을 다시 실행해야 하며, 이는 계산 비용이 많이 들고 시간이 많이 소요
  • 그러나 iBLAST는 이전 BLAST 검색 결과를 활용하여 새롭게 추가된 시퀀스에 대해서만 검색을 수행하고, e-value와 같은 중요한 통계를 재계산한 후 이러한 결과를 병합하여 업데이트된 검색 결과를 생성
  • 이 방법은 NCBI BLAST와 동일한 결과를 제공하면서 상당한 계산 비용 절감을 보여주어 효율적인 생물학적 발견을 위한 유용한 도구


Methods

  • iBLAST의 증분 업데이트 메커니즘은 먼저 마지막 검색 이후 데이터베이스에 추가된 새로운 시퀀스에 대해 BLAST 검색을 수행하는 것
  • 다음 업데이트된 데이터베이스 크기를 기반으로 새로운 결과와 이전 결과에 대한 중요한 통계, 예를 들어 e-value를 재계산
  • 시스템은 이러한 결과를 병합하여 업데이트된 검색 결과를 생성
  • 이 과정은 iBLAST가 데이터베이스 성장의 분수인 δ를 고려할 때 전체 NCBI BLAST 검색보다 (1+δ)/δ 배 더 빠르게 작동하기 때문에 훨씬 더 효율적
  • 시스템의 구조는 NCBI BLAST 명령줄 도구의 최신 버전과 통합되는 Python 모듈을 포함하여 기존 BLAST 사용자의 호환성과 사용 용이성을 보장
  • iBLAST는 광범위한 시퀀스 검색을 포함하는 대규모 생물정보학 프로젝트에 특히 유용하며, 이러한 작업에 필요한 계산 비용과 시간을 크게 줄임

BLAST concepts and statistics

Core concepts of a BLAST result: Hit, HSP, score, and e-value.

  • BLAST 검색 결과의 핵심 개념에는 히트(Hit), 고득점 쌍(HSP), 점수(Score), 그리고 기대값(e-value)이 포함

  • 히트(Hit): BLAST 검색을 수행할 때, 쿼리 시퀀스와 유의미한 정렬을 생성하는 대상 데이터베이스 내의 시퀀스들을 ‘히트’라고 정의, 각 히트는 쿼리 시퀀스와 유사성을 공유하는 하나의 대상 시퀀스를 나타냄

  • 고득점 쌍(High Scoring Pair, HSP): 히트 내에서, 쿼리와 대상 시퀀스 사이의 특정 지역적 정렬을 고득점 쌍이라고 정의, HSP는 쿼리와 히트 사이에서 가장 높은 점수를 얻은 정렬 부분을 나타냄, 하나의 히트는 여러 개의 HSP를 포함할 수 있음

  • 점수(Score): HSP의 점수는 정렬된 시퀀스 쌍 사이의 유사성 정도를 수치적으로 나타냄, 높은 점수는 높은 유사성을 의미하며, 점수 계산은 일치, 불일치, 갭 존재 등의 요소를 고려하여 이루어짐

  • 기대값(e-value): e-value는 특정 HSP가 데이터베이스의 크기와 같은 다른 통계적 매개변수를 고려하여 랜덤한 일치로 발생할 확률을 나타냄, 낮은 e-value는 HSP가 우연히 발생할 가능성이 낮음을 의미하며, 따라서 해당 HSP가 더 유의미하다고 간주

  • 이러한 개념들은 BLAST 검색 결과의 해석과 이해에 중요하며, 특히 e-value는 결과의 유의미함을 평가하는 데 주로 사용

BLAST statistics for e-value computation

  • BLAST에서 e-value 계산을 위한 통계는 주로 Karlin-Altschul 통계와 Spouge 통계 두 가지 방법을 사용

Karlin-Altschul Statistics

  • 이 방법은 e-value를 계산할 때 사용되며, 특정 HSP가 얻을 수 있는 점수(S)와 데이터베이스 크기, 쿼리의 길이 등을 고려하여 e-value를 계산
  • Karlin-Altschul 통계는 e-value를 E=e^( −λ(S−μ) ) = Km′n′e^(−λS) 로 정의
  • 여기서 m′과 n′은 쿼리와 데이터베이스의 유효 길이이며, λ, K, μ는 각각 통계적 매개변수
  • 길이 조정값 l은 다음과 같은 공식을 만족 l= λ/1 ln(K(m−l)(n−Nl))
  • 여기서 λ, K는 통계적 매개변수로, BLAST 검색에 사용되는 고정된 값
  • 이러한 방식으로 Karlin-Altschul 통계는 검색 결과의 e-value를 계산함으로써, 특정 HSP가 무작위로 발생할 확률을 정량화
  • 낮은 e-value는 HSP가 우연히 발생할 가능성이 낮으며, 따라서 해당 HSP가 더 유의미하다고 간주
  • 이 통계 방법은 BLAST 검색 결과의 신뢰성과 정확성을 높이는 데 중요한 역할, 주로 blastn과 tblastx BLAST 프로그램에서 사용

Spouge Statistics

  • Spouge 통계는 Karlin-Altschul 공식을 발전시킨 것으로, 유효 길이를 직접 계산하는 대신 유한 크기 교정(Finite Size Correction, FSC)을 적용
  • Karlin-Altschul 통계에서 길이 조정값 l을 계산한 후 이를 사용하여 데이터베이스와 쿼리의 유효 길이를 계산하는 대신, Spouge 통계는 유한 크기 교정(Finite Size Correction, FSC)을 적용
  • FSC는 l을 직접 추정하는 대신, E[m−LI(y)]+[n−LJ(y)]+를 사용하여 (m−l)(n−Nl)의 대체 측정값인 ‘영역(area)’을 추정
  • m은 쿼리의 실제 길이, n은 데이터베이스의 실제 길이, N은 데이터베이스 내의 시퀀스 개수
  • e-value를 E = area * K e^{- λ S} * db_scale_factor로 계산
  • db_scale_factor는 데이터베이스 스케일 팩터로, n_0 / m_0 로 계산
  • n_0 과 m_0 은 각각 데이터베이스와 쿼리의 유효 길이
  • area는 유효 길이의 대체 측정값이며, db_scale_factor는 데이터베이스 크기에 대한 스케일 팩터, K와 λ는 BLAST 검색에 사용되는 통계적 매개변수, S는 HSP의 점수 의미
  • Spouge 통계를 사용함으로써 BLAST는 데이터베이스 크기와 같은 외부 요인의 변화가 검색 결과의 통계적 유의성에 미치는 영향을 더 정확하게 반영할 수 있게 됨
  • BLAST 검색 결과를 더 신뢰성 높이며 특히 큰 데이터베이스에서의 검색에 유용
  • 이 방법은 주로 blastp, blastx, tblastn 프로그램에서 사용

Existing e-value correction software and their features

  • 기존 e-value 수정 소프트웨어와 그 특징에 관하여, mpiBLAST와 NOBLAST라는 두 가지 주요 도구가 있고 이들은 BLAST 결과의 e-value를 보정하는 데 사용

  • mpiBLAST: mpiBLAST는 NCBI BLAST의 병렬 구현으로, 데이터베이스를 여러 부분으로 나누어 각각에 대해 병렬로 BLAST 검색을 수행
    ** e-value 보정을 위해, mpiBLAST는 전체 데이터베이스에 대한 사전 지식이 필요하며, 이를 각 병렬 작업에 전달하여 정확한 e-value 통계를 제공

  • NOBLAST: NOBLAST는 분할된 데이터베이스를 사용할 때 결과를 합칠 필요가 있을 때 e-value를 보정하는 도구, 그러나 NOBLAST는 Spouge 통계를 지원하지 않으며, Karlin-Altschul 통계에 대해서만 정확한 e-value 통계를 제공

  • iBLAST는 이러한 도구들과 다르게 시간적으로나 공간적으로 데이터베이스가 추가될 때 BLAST 결과를 합치는 기능을 제공, iBLAST는 기존의 BLAST 결과를 재사용하고, 새로 추가된 데이터베이스 부분에 대해서만 검색을 수행한 후, 이러한 새로운 검색 결과의 e-value를 보정하여 최종 결과를 생성합, 이 방식은 특히 데이터베이스의 성장으로 인해 BLAST 검색 결과를 자주 업데이트해야 하는 대규모 생물정보학 프로젝트에 유용

  • iBLAST는 과정을 간소화하고 사용자가 쉽게 BLAST 검색 결과를 최신 상태로 유지할 수 있도록 도와줌
    ** mpiBLAST와 NOBLAST가 제공하는 기능에 비해, iBLAST는 더 광범위한 시나리오에서 e-value 보정을 지원하며, 사용자가 기존 검색 결과를 효율적으로 재사용할 수 있게 함​​.

Redundancy in data vs. redundancy in computation.

  • 데이터의 중복성은 데이터베이스 내에 중복된 정보나 시퀀스가 존재하는 것을 의미
  • 이는 데이터 저장 공간을 불필요하게 차지하며 데이터 처리 시간을 증가시킬 수 있음
  • 반면, 계산의 중복성은 특정 계산 작업이 불필요하게 반복되어 수행되는 것

  • 예를 들어, 유전체 데이터베이스가 지속적으로 성장함에 따라 BLAST와 같은 시퀀스 검색 도구를 사용할 때, 데이터베이스 업데이트마다 처음부터 전체 검색을 다시 실행하는 것은 많은 계산 자원을 낭비하는 일

  • iBLAST 시스템은 이러한 계산의 중복성 문제를 해결하기 위해 개발
  • iBLAST는 이전 BLAST 검색 결과를 재활용하고 데이터베이스에 새로 추가된 부분에 대해서만 검색을 수행한 후, 새로운 검색 결과의 e-value를 보정하여 최종 결과를 생성

  • 이 방법은 데이터베이스의 크기가 증가함에 따라 발생할 수 있는 계산의 중복성을 크게 줄여주며, 전체 데이터베이스에 대한 검색을 다시 실행하는 것보다 훨씬 효율적

  • 데이터의 중복성은 데이터 관리와 저장의 측면에서의 문제를 일으키는 반면, 계산의 중복성은 주로 시간과 자원의 낭비와 관련
  • iBLAST와 같은 도구는 계산의 중복성을 최소화하여 생물정보학 연구에서 시간과 계산 자원을 절약할 수 있는 방법을 제공

e-value correction in an incremental setting

  • iBLAST 시스템에서 새로운 데이터베이스 시퀀스가 추가될 때 e-value를 정정하는 방법
  • 이 과정은 Karlin-Altschul 통계와 Spouge 통계 모두에 필요한 실제 데이터베이스 길이(기본/잔여물의 총 수)를 사용

e-value correction for Karlin-Altschul statistics

  • n_t = n_c + n_d : 업데이트된 데이터베이스의 실제 길이는 현재 데이터베이스 길이(n_ c)와 새로 도착한 시퀀스의 길이(n_d)의 합
  • N_t = N_c + N_d : 업데이트된 데이터베이스의 시퀀스 총수는 현재 데이터베이스의 시퀀스 수(N_c)와 새로운 부분의 시퀀스 수(N_d)의 합
  • l= (a/l) * ln(K(m−l)(n_c + n_d −(N_c + N_d)*l))+b : 새로운 데이터베이스 길이를 사용하여 효과적인 길이 l을 재계산하는 고정점 방정식. 여기서 a,b,K는 통계적 매개변수
  • E=e^(−λ(S−m)) =K(m−l)((n_c + n_d)−(N_c + N_d)l)e^(−λS) : 모든 매치에 대한 e-value를 처음부터 다시 계산하는 수식
  • E_total =E_part + Ke^(−λS)*(D_total − D_part): 현재 값에서 e-value를 정정할 때, 부분적으로 효과적인 검색 공간 D_part 과 전체 효과적인 검색 공간 D_total 을 사용하여 새로 계산된 효과적인 검색 공간을 이용해 e-value를 재조정하는 수식

    e-value correction for Spouge statistics

  • E_part =area * e^(−λS) * (n_part/m) 및 E_total =area * e^(−λS) * (n_total/m) : 새롭게 추가된 데이터베이스 부분과 전체 데이터베이스에 대한 실제 길이를 사용하여 e-value를 계산하는 수식
  • E_total = E_part * (n_total/n_part) : 이전에 계산된 e-value(E_part)를 새로운 전체 데이터베이스 길이를 기반으로 재조정하는 수식

Merging two search results with correct e-value statistics

  • 정정된 e-value를 가진 현재 및 새로운 검색 결과는 단일 정렬된 목록으로 합쳐짐
  • iBLAST는 NCBI BLAST가 놓칠 수 있는 더 나은 점수를 가진 히트를 보고하기 때문에, 단순히 최대 타겟 시퀀스(max_target_seqs)의 히트만을 보고하는 것은 NCBI BLAST에서 낮은 점수를 가진 히트를 놓칠 수 있음
  • 따라서, 2배의 max_target_seqs 히트를 저장하고 보고
  • 모든 통계적 매개변수는 전체 데이터베이스 크기에 따라 재조정되어 e-value를 재계산하거나 재조정
  • 히트는 e-value의 오름차순(점수의 내림차순)으로 선택

    iBLAST implementation

    *iBLAST는 NCBI BLAST 코드를 확장하여 BLAST 검색을 수행하도록 개발되었음, 이는 NCBI BLAST 프로그램을 블랙박스 루틴으로 사용하는 파이썬 래퍼 스크립트로 구성

  • 증분 로직 모듈:
    ** SearchRecord lookup (검색 기록 조회): 이 하위 모듈은 레코드 데이터베이스를 사용하여 기존의 검색 결과를 찾음. 사용자가 새로운 BLAST 검색을 요청할 때, 이 모듈은 먼저 데이터베이스에서 해당 쿼리에 대한 이전 검색 결과가 있는지 확인. 이 과정을 통해 새로운 검색을 수행하기 전에 기존의 결과를 재활용할 수 있는지 판단.
    ** Delta and past database creation (델타 및 과거 데이터베이스 생성): 이 하위 모듈은 현재 데이터베이스와 과거 인스턴스를 비교하여 델타 데이터베이스를 구축. 델타 데이터베이스는 두 데이터베이스 인스턴스 간의 차이점으로 구성되며, 새로 추가된 시퀀스만 포함. 이 모듈은 델타 데이터베이스에 대해 BLAST 검색을 수행하여 새로운 결과를 얻음.
    ** Statistics (통계): 이 하위 모듈은 과거 검색 결과와 새로운 증분 검색 결과를 읽고, 두 결과에 포함된 e-value를 재평가. 그런 다음, 재계산 또는 재조정된 e-value를 바탕으로 두 결과를 합침. 이 과정은 업데이트된 데이터베이스 크기에 기반하여 e-value를 정확하게 조정함으로써, 검색 결과의 정확성과 신뢰도를 보장.
    ** SearchRecord writer (검색 기록 작성자): 이 모듈은 업데이트된 검색 결과를 NCBI BLAST 형식 중 하나로 작성. 이는 사용자가 다양한 분석 도구 및 파이프라인과 호환 가능한 형식으로 결과를 받을 수 있게 해줌.

Record database for storing incremental search results

  • 레코드 데이터베이스: 사용자가 BLAST 검색을 수행할 때, iBLAST는 데이터베이스 인스턴스와 검색 결과에 관한 메타 정보(예: 데이터베이스의 크기와 파일 이름 목록)를 경량 SQLite 데이터베이스에 저장. iBLAST는 특정 쿼리와 데이터베이스에 대한 가장 최근 결과만 저장하여 저장 공간을 최소화.

Case studies

Case study 1: Method verification.

  • 목적: iBLAST와 NCBI BLAST의 시퀀스 검색 정확도 비교
  • 방법: 100개의 Bombus impatiens 시퀀스에 대해 blastn(핵산 데이터베이스)과 blastp(단백질 데이터베이스)를 사용하여 NCBI 데이터베이스의 성장을 고려하여 검색을 수행
  • 결과: iBLAST는 세 시간 기간 동안 NCBI BLAST와 동일한 정확도를 보여주며, 데이터베이스 크기가 증가함에 따라 필요한 검색 부분만을 대상으로 하여 효율성을 높임

Case study 2: Updating a query re-annotation of a novel transcriptomics dataset.

  • 목적: 새로운 검색을 기존 검색에 시간적으로 추가하는 가치 평가
  • 방법: 아직 NCBI BLAST 데이터베이스에 등록되지 않은 독창적인 Oak gall wasp의 venom gland transcriptome 데이터셋을 사용하여 BLAST 검색 수행
  • 결과: iBLAST는 이전 검색 결과를 재활용하여 새로운 검색 결과와 병합함으로써, 단일 프로세서 코어에서 수행할 경우 몇 달이 걸릴 수 있는 검색을 효과적으로 단축

    Distributing workload across nodes

  • BLAST 검색 작업을 여러 컴퓨팅 노드에 효율적으로 분산을 위해 17,927개의 쿼리를 포함하는 데 노보(de novo)로 조립된 transcriptome 데이터셋에 대한 BLAST 검색이 수행되었으며, 이 작업을 640개의 코어가 있는 20개의 컴퓨팅 노드에 분산. 각 노드는 쿼리 파일 하나를 할당받아 동일한 데이터베이스에 대해 서브셋(subset)을 실행. ** 작업 부하를 노드 간에 균형 있게 분배하기 위해, 쿼리들의 순서를 무작위화하고 각 파티션마다 대략 동일한 수의 레지듀(residues)를 가지도록 쿼리들을 파티셔닝. 이 방법은 각 파티션에 대략 동일한 수의 쿼리를 단순히 배치하는 직선적 접근법과 비교. 레지듀 기반 파티셔닝 전략은 모든 쿼리 파일의 계산이 대략 동시에 완료되도록 하여, 작업 부하가 노드 간에 균등하게 분배되도록 하는 데 도움.

Case study 3: Taxon-based incremental approach

  • 목적: 특정 분류군에 대한 검색을 추가함으로써 계산 시간을 절약하는 방법 평가
  • 방법: Oak trees의 gall wasp인 hedgehog gall wasp의 venom gland transcriptome 분석을 위해 가장 가까운 친척들의 transcriptome에 대해 개별적인 BLAST 검색을 수행하고 iBLAST를 사용하여 결과를 병합
  • 결과: iBLAST를 사용한 분류군 기반 접근법은 계산 효율성을 높이고 생물학적으로 관련된 결과를 빠르고 비용 효과적으로 얻을 수 있음을 보여줌

Results

Case study 1: Method verification and performance

Verification

  • 검증: iBLAST가 NCBI BLAST와 동일한 결과를 제공하는지 확인, 100% e-value 일치 및 히트 일치 보고
  • 성능: 데이터베이스 크기 증가에 따른 iBLAST의 성능 향상, 약 3배에서 5배의 속도 향상 보여줌

Case study 2: Large-scale alignment tasks on novel datasets

  • iBLAST와 NCBI BLAST를 사용하여 새로 얻은 gall wasp transcriptome 데이터셋 검색 수행
  • 데이터베이스 크기 증가에 따라 iBLAST가 NCBI BLAST보다 3.1배 빠름
  • 쿼리 파티셔닝을 통한 노드 간 작업 부하 분배의 효과 관찰

Case study 3: Taxon-specific searches to expedite informatics

  • 여러 분류군 특정 데이터베이스를 병합할 때 iBLAST의 정확성 확인
  • 분류군 특정 접근법이 시간 효율성과 계산 비용 측면에서 훨씬 유리함을 보여줌

iBLAST finds better scoring hits that are missed by NCBI BLAST

  • iBLAST가 NCBI BLAST가 놓친 더 높은 점수의 히트를 찾아내는 추가적인 이점 제공

Discusion

  • iBLAST는 e-value 정정과 증분 BLAST 검색을 가능하게 하는 도구로, NCBI BLAST의 결과를 개선
  • iBLAST는 계산 시간과 비용을 절감하면서도 정확성을 유지하며, 다른 빠른 BLAST 구현체를 래핑하여 성능을 더욱 향상시킬 수 있음
  • 시퀀스 데이터베이스가 지속적으로 성장하는 현 시점에서 iBLAST는 시퀀스 유사성 검색 도구에 대한 새로운 접근 방식을 제공함