한줄 요약: IsarPipeline은 MMseqs2와 PSI-BLAST를 결합하여(및 메모리 잠금 품..) 단일 쿼리 정렬의 런타임을 53초로 단축시키며, PSI-BLAST에 비해 성능이 비슷하거나 약간 더 나은 PSSM 파일을 생성함  

짧은 요약(Abstract) :    
* 여러 생물정보학 및 계산 생물학 모델에서 단백질의 기능이나 구조를 예측하기 위해 사용되는 기계학습 모델들은 PSI-BLAST에 의해 생성된 다중 시퀀스 정렬이나 위치 특이적 점수 행렬의 요약된 진화 정보에 의존함  
* 단백질 구조 및 기능 예측에 사용되는 현재 절차는 계산적으로 많은 자원을 소모하고 시간이 많이 걸림  
* 주된 문제는 PSI-BLAST 소프트웨어가 현재 시퀀스 데이터베이스를 배치로 로드하고 쿼리 시퀀스와 유사한 시퀀스 정렬을 검색해야 한다는 것임  
* 이로 인해 중간 크기의 단백질에 대해 평균 40-60분의 런타임이 소요됨  
* 이 평균 런타임은 소프트웨어를 실행하는 하드웨어에 따라 엄격하게 달라짐  
* 문제는 생물학적 시퀀스 데이터 풀이 시간이 지남에 따라 기하급수적으로 증가하여 PSI-BLAST의 런타임도 증가한다는 점에서 더욱 문제가 됨  
* 주목할 만한 해결책은 현재 과정을 100배 빠르게 만들겠다고 주장함  
* 충분한 메모리가 주어진 MMseqs2 방법은 전체 데이터베이스를 메모리에 로드하고 특정 휴리스틱을 적용하여 관련된 시퀀스 집합을 검색함  
* 그러나 이 솔루션은 원하는 PSI-BLAST 정렬 및 PSSM 프로파일 데이터 형식으로 최종 출력을 직접 생성하는 데에는 사용할 수 없음  
* 이 연구 프로젝트에서는 각 도구의 런타임 성능을 분석함  
* 또한 MMseqs2와 PSI-BLAST를 결합하여 PSI-BLAST보다 두 자릿수 더 빠른 강력한 최적화된 매우 빠른 하이브리드 정렬 도구를 얻기 위한 파이프라인을 구축함  
* C++로 구현되었으며 MIT 라이선스에 따라 무료로 제공됨  
* 저자들의 파이프라인의 출력은 이전에 구축된 두 개의 예측 모델에서 평가됨  

Useful sentences :


Paper link
Lecture link


단어정리

  • convertail: 변환하는 모듈
  • SOM: Supplementary Online Material: 논문 본문에 포함되지 않은 추가적인 정보, 데이터, 분석, 그림 등을 담고 있는 온라인 부록을 의미

1. INTRODUCTION

  • 여러 시퀀스 정렬 방법이나 MSA-방법들은 진화적으로 관련된 시퀀스들의 정렬을 위한 알고리즘 솔루션 집합임
  • DNA, RNA 또는 단백질 시퀀스에 적용될 수 있음
  • 이러한 알고리즘들은 돌연변이, 삽입, 삭제 및 재배열과 같은 진화적 사건을 특정 조건 하에 고려하여 설계됨
  • 최근 네이처 출판물에서 Van Noorden R. 등은 생물학 분야에서 가장 널리 채택된 모델링 접근 방식이 다중 시퀀스 정렬 방법을 사용한다고 언급함
  • 이 진술은 “Gapped BLAST와 PSI-BLAST” 도구의 출판된 원고에서 Altschul 등에 의해 지지됨, 이는 모든 시간 동안 11번째로 가장 많이 인용된 과학 논문으로 순위가 매겨짐
  • 실제로 이 중요한 모델링 도구 MSA의 개발은 복잡한 계산 및 생물학적 문제 모두를 해결해야 했음

  • MSA는 항상 NP-완전 문제로 인식되었으며, 이는 지난 40년 동안 100가지 이상의 대안 알고리즘이 정확한 MSA를 제공하기 위해 구축되었음을 이유로 듦

  • 현대 계산 생물학에서, 특히 단백질과 그들의 특성 예측 분야에서, 시퀀스 정렬은 거의 모든 기계학습 방법에 대한 표준 입력 형태임

  • 그러나 이 방법론은 계산적으로 많은 자원을 소모하고 시간이 많이 걸림

  • 현재 MMseqs2는 이러한 거대한 데이터셋을 다루면서 상당한 하드웨어 요구 사항을 대가로 이 문제를 해결하는 유일한 MSA 기반 대안 솔루션으로 보임
  • 저자들은 이 논문에서 이 두 가지 최첨단 방법을 결합하여 빠르게 광범위한 단백질 시퀀스 정렬과 해당 PSSM 프로필을 생성하는 최적화된 빠른 하이브리드 정렬 솔루션을 소개함

  • 이 원고에서는 파이프라인 아키텍처 구성 요소를 설명하고, 두 도구(MMseqs2 대비 PSI-BLAST) 간의 런타임 비교를 제공하며, 마지막으로 IsarPipeline 출력의 두 기계학습 모델(TMSEG 및 REPROF)에 대한 평가 결과를 제시함

  • 모든 결과는 룩셈부르크 대학에서 부여한 서버에서 수행됨
  • 기계의 주요 특성은 다음과 같이 요약됨: 196Gib의 메모리 크기와 SSE4.1 명령 세트를 지원하는 4개의 코어를 가진 인텔 제온 E312xx CPU


2. BACKGROUND

  • IsarPipeline의 세 가지 주요 요소는 MMseqs2, PSI-BLAST 및 생성된 PSSM 프로파일임

  • MMseqs2는 매우 큰 단백질 시퀀스 데이터셋을 검색하고 클러스터링하기 위해 사용되는 극도로 최적화된 확장 가능한 소프트웨어임
  • 오픈소스 크로스플랫폼 도구로, 최신 CPU 아키텍처의 전체 성능을 활용하여 C++로 개발되었으며, 특히 SIMD 최적화된 명령어 세트 처리 단위를 사용함

  • 이 도구는 단백질 시퀀스의 정렬을 계산하기 위해 SIMD 가속 스미스-워터맨 정렬 알고리즘을 구현함

  • PSI-BLAST는 위치 특이적 반복 기본 지역 정렬 검색 도구를 의미함
  • 동적 프로그래밍 최적화 패러다임에 의해 구동되는 다중 시퀀스 정렬 알고리즘을 실행하는 소프트웨어로, 주어진 단백질 시퀀스 데이터베이스를 검색함
  • 쿼리 시퀀스를 주어, 알고리즘은 미리 정의된 임계값을 통과하는 유사 시퀀스를 검색함
  • 이 임계값 기반 계산 유사성 방법은 단백질-단백질 BLAST를 사용하여 지역 정렬의 영역을 식별하고, 검색된 시퀀스 가족으로부터 PSSM을 구성하는 데 사용됨

  • 이 행렬은 후속 반복의 소프트웨어에서 데이터베이스를 더 검색하고 더 많은 히트를 검색하는 데 사용되며, 그런 다음 PSSM 자체를 업데이트하고 개선하는 데 사용됨

  • PSSM은 위치 특이적 점수 행렬을 의미하며 프로파일 행렬로도 불림
  • PSSM 프로파일은 데이터베이스의 관련된 모든 정렬된 단백질 시퀀스에 대한 주어진 단백질 시퀀스의 서열에 대한 통계적 표현을 포함함
  • 프로파일은 정렬에서 보존 패턴을 포착하고 각 위치에 대한 점수로 저장함
  • 여기서 높은 점수는 보존도가 높은 위치에 할당되고 낮은 점수는 보존도가 낮은 위치에 할당됨
  • 따라서 행렬 표현에는 단백질의 진화 정보가 포함됨
  • PSSM은 생물정보학과 계산 생물학 분야에서 필수적임
  • 그러나 이러한 PSSM의 계산은 상당한 계산 능력과 런타임을 요구하기 때문에 감당하기 어려움
  • 새로운 기계학습 방법이나 통계 분석을 구축하는 과정에서 이러한 계산 비용이 두드러짐
  • 이러한 샘플은 연구를 시작하기 전에 몇 주 동안 처리해야 하므로 매우 불편함


3. DATASET

  • 이 논문에서의 런타임 측정은 아미노산 시퀀스 정렬 검색에 관한 것으로, 데이터베이스 인덱싱에 필요한 시간(~1시간 20분)을 제외함
  • 보다 신속한 실행을 위해, UniProt 참조 클러스터에서 시퀀스 동일성이 90%인 샘플(uniref90 2019_02)을 대상으로 함
  • 전체 uniref90은 대략 250Gib 크기의 인덱스 테이블을 생성할 것이기 때문에, RAM에 맞출 수 있는 데이터베이스의 인덱스 테이블이 필요함
  • 저자들의 테스트 기계 메모리에 맞는 무작위 샘플(~6800만 단백질)을 uniref90에서 실행함
  • 이 샘플은 181Gib 크기의 인덱스 테이블을 생성하여 저자들의 테스트 기계 메모리에 맞음


4. ISAR PIPLELINE ARCHETECTURE

  • IsarPipeline은 MMseqs2와 PSI-BLAST를 결합하여 쿼리 시퀀스 세트의 프로파일을 빠르게 생성함
  • 이 목표를 달성하기 위해 IsarPipeline을 실행하기 전에 검색할 데이터베이스를 사전 처리하는 것이 중요함
  • 사전 처리 단계는 대규모 데이터셋의 경우 수백 기가바이트에 이를 수 있는 인덱스 테이블을 생성함
  • 이 단계는 이후에 정렬을 가속화하기 위해 필수적임
  • 인덱스 테이블을 생성하는 것은 IsarPipeline을 통해 데이터베이스를 검색하는 데 필수적이지 않음
  • 검색 명령은 파이프라인 실행을 시작하기 바로 전에 인덱스 테이블을 생성함
  • 그러나 인덱스 테이블을 미리 생성하고 저장하는 것이 권장됨

  • 이렇게 하면 검색 명령이 동일한 데이터베이스에서 파이프라인의 여러 실행을 시작할 때마다 인덱스 테이블을 각 검색에 대해 생성하지 않아도 됨

  • 사전 처리 단계의 출력은 검색할 주요 대상 데이터베이스의 인덱스 테이블임
  • 이것은 IsarPipeline이 실행되는 입력으로, PSSM 프로파일을 최종적으로 생성하기 위해 연속적인 모듈 세트를 실행함
  • 첫 번째로 시작하는 것은 “사전 필터 모듈”임
  • 이 모듈은 MMseqs2의 주요 구성 요소를 구성함
  • 사전 필터링 모듈은 모든 쿼리 시퀀스와 모든 데이터베이스 시퀀스 사이의 모든 연속된 k-mer 일치에 대한 무간극 정렬 점수를 계산하고 시퀀스별로 가장 높은 점수를 반환함
  • 사전 필터 k-mer 일치 단계는 높은 속도와 민감도의 핵심임
  • 같은 대각선상에서 일치하는 연속적인 짧은 단어(즉, k-mer)를 감지함
  • 대각선은 쿼리와 대상 시퀀스에서 두 유사한 k-mer의 위치 차이임
  • 사전 필터링 모듈이 완료되면, 모듈이 검색할 수 있는 시퀀스의 최대 수 N에 도달하지 않는 각 쿼리 시퀀스에 대한 최적의 일치를 생성함

  • 이 숫자는 파이프라인에 인수로 제공될 수 있으며, 저자들의 실험에서는 쿼리 시퀀스당 1000개의 정렬된 시퀀스로 설정됨

  • 일치하는 항목은 그 다음 “정렬 모듈”로 전달됨
  • 이 모듈은 첫 번째 모듈에서 사전 필터링 점수에 대한 임계값을 통과하는 모든 시퀀스 쌍을 구현하며, 각 시퀀스 쌍을 병렬로 정렬하여 한 번에 한 코어당 하나의 정렬을 계산함
  • 이 단계는 SIMD 명령 세트를 사용하는 벡터화된 프로그래밍 알고리즘을 사용하여 구현됨
  • 이때 SSE4.1 명령 세트 요구 사항이 사용됨
  • 마지막으로 이 모듈은 시퀀스 정체성, 정렬 커버리지, 정렬의 e-값과 같은 정렬 통계를 계산함
  • 그런 다음 이러한 통계는 “convertalis모듈” 및 “파싱 모듈”로 전달되어 최적화된 알고리즘을 사용하여 FASTA 형식으로 출력을 변환함
  • 이렇게 생성된 출력을 황금 DB라고 하며, 최대 1,000개의 시퀀스를 포함할 수 있음
  • 이 시퀀스들은 PSI-BLAST 모듈로 공급되어 최종 PSSM 프로파일을 생성함
  • 이 과정은 자세한 구성 요소 설명과 개략도와 함께 SOM의 섹션 1에서 참조할 수 있음


5. SUPER-FAST SEQUENCE ALIGNMENT

  • IsarPipeline 검색의 각 모듈 런타임 분석에서 인덱스 테이블을 로드하는 것이 전체 런타임의 약 90%를 차지하는 것으로 나타남
    8 이는 주로 사전 필터링 및 Convertalis 모듈 실행 동안 제한됨

  • 따라서 전체 DB를 RAM에 미리 로드한 다음 각 검색 시 직접 사용하고 검색 결과를 변환하면 런타임이 크게 감소함

  • 하나의 해결책은 전체 데이터베이스를 RAM에 로드하고 페이지를 그곳에 잠그는 것임
  • 검색 중에는 디스크에서 다시 로드하는 대신 잠긴 DB에서 시퀀스를 매핑함
  • 이를 위해 “vmtouch”라는 유지 관리가 잘 되는 소프트웨어를 사용함
  • 이 도구는 인덱스 테이블을 RAM에 로드하고 페이지를 그곳에 잠그는 데 사용됨

  • 다음 명령을 통해 실행할 수 있음 sudo /usr/local/bin/vmtouch -l -d -t targetDB.idx

  • 명령에는 두 가지 주요 매개변수가 있음: 페이지를 잠그는 “l”과 데몬으로 실행하는 “d”
  • 또한 명령은 루트 권한을 가져야 함
  • 이유는 운영 체제에 의해 적용되는 “최대 잠금 메모리” 제약 때문임
  • 일반적으로 64kb임
  • 그렇지 않으면 데이터베이스가 RAM에 로드되지만 거기에 잠기지는 않음

  • 이 문제는 sudo 환경 변수에 전체 경로를 포함시키고 루트 권한으로 프로세스를 실행하거나 sudo를 사용하지만 실행 파일의 전체 경로를 사용하여 명령을 실행함으로써 해결될 수 있음

  • 이 해결책과 “–db-load-mode 2”를 매개변수 값으로 제공함으로써 IsarPipeline을 사용하여 평균 길이 단백질 시퀀스의 PSSM 파일을 53초 만에 생성할 수 있게 됨


6. EVALUATION AND RESULTS

  • MMseqs2 대비 PSI-BLAST: 런타임 벤치마킹
  • 단일 쿼리 단백질을 사용하여 각 방법의 실행 시간을 비교할 때, 단백질의 아미노산 시퀀스 길이가 PSI-BLAST의 런타임에 영향을 미치는 반면 MMseqs2에는 영향을 미치지 않음
  • PSI-BLAST의 런타임은 쿼리 시퀀스 내의 잔기 수가 증가함에 따라 증가하는 반면, MMseqs2의 런타임은 일정함
  • 그러나 일괄 처리의 경우 실험은 반대 결과를 보여줌
  • 일괄 쿼리에 포함된 시퀀스 수가 증가함에 따라 PSI-BLAST의 런타임에 큰 영향을 미침
  • 반면 MMseqs2는 거의 영향을 받지 않음
  • MMseqs2의 런타임은 22분에서 32분 사이이며 평균 런타임은 약 30분임

  • PSI-BLAST의 런타임은 선형적으로 증가하며, 이는 주로 쿼리 시퀀스를 순차적으로 처리하기 때문임

  • 단일 쿼리 정렬의 경우 PSI-BLAST가 더 빠르지만 일괄 시퀀스 처리 측면에서 MMseqs2가 훨씬 더 잘 확장됨

  • 이러한 특징은 더 빠른 일괄 시퀀스 정렬 방법을 구축하기 위해 활용됨

  • 파이프라인 평가
  • 저자들의 IsarPipeline의 출력 결과를 평가하는 한 가지 방법은 저자들의 도구 출력을 사용하는 기존 기계학습 모델의 예측이 어떻게 변하는지 평가하고 파이프라인이 예측에 부정적인 영향을 미치는지 여부를 확인하는 것임

  • 저자들은 TMSEG와 REPROF라는 두 가지 기계학습 방법에 대해 파이프라인을 테스트함

  • TMSEG는 단백질에서 트랜스멤브레인 세그먼트를 예측하는 도구임
  • 이 방법에 대해 265개의 고유 단백질이 PSI-BLAST와 IsarPipeline을 사용하여 평가됨
  • 평가할 첫 번째 메트릭 차원은 PSSM 파일을 얻는 데 필요한 런타임임
  • PSI-BLAST는 PSSM을 생성하는 데 48.5시간이 걸림
  • IsarPipeline은 단지 30분이 필요함

  • 런타임이 약 100배 줄어듦

  • 두 번째 메트릭 차원은 두 출력 간의 문자 단위 유사성임
  • 그림 3-b는 PSI-BLAST PSSM에서 생성된 0.95 이상의 문자 단위 유사성 백분율이 IsarPipeline에서 생성된 것보다 낮음을 보여줌
  • 그러나 PSI-BLAST의 0.9 유사성 결과는 IsarPipeline 결과보다 훨씬 높음
  • 통계적 관점에서 전체 유사성 평균을 비교하면 IsarPipeline 결과의 유사성 평균은 0.830이며 표준편차는 0.125임
  • PSI-BLAST 결과의 유사성 평균은 0.832이고 표준편차는 0


7. CONCLUSION

  • 이 연구 작업의 결과에서 MMseqs2가 단일 쿼리 검색의 경우 PSI-BLAST보다 느리게 실행되는 것으로 나타났지만 일괄 처리의 경우 매우 강력한 것으로 드러남
  • 저자들은 이러한 특성을 활용하여 MMseqs2와 PSI-BLAST를 결합하여 대규모 쿼리 단백질 시퀀스 배치를 검색할 때 PSI-BLAST보다 2자리 수 이상 빠른 IsarPipeline을 구축함
  • 저자들은 파이프라인의 출력 결과를 평가하고 PSI-PLAST의 결과와 비교함
  • IsarPipeline의 성능이 PSI-BLAST 결과와 적어도 비교할 수 있으며 종종 약간 더 나은 것으로 나타남
  • 그 후 저자들은 단일 쿼리 정렬을 거의 즉시 만드는 해결책을 소개함
  • “vmtouch”를 사용하여 데이터베이스를 각 검색에 대해 다시 로드하는 대신 인덱스 테이블을 RAM에 로드하고 페이지를 잠글 수 있음
  • 결과적으로 IsarPipeline을 사용하여 평균 길이 시퀀스(~450 AA)에 대해 53초 만에 런타임 속도를 달성함
  • 정렬은 PSI-BLAST가 수십 분 동안 생성하는 행렬과 거의 동일한 통계 정보를 포함하는 PSSM 파일을 생성함