스템로크

생물정보학에서 스템로크는 Pair 확률적 문맥 자유 문법(Pair statistic context-free grammars)으로 알려진 RNA 구조의 확률론적 모델에 기초한 다중 RNA 배열 및 RNA 구조 예측을 위한 오픈 소스 소프트웨어이다.Stemloc는 동일한 동기로 이전 방법에 비해 향상된 시간과 공간 비용과 함께 RNA 배열의 구조를 예측하고 정렬하려고 시도합니다.결과 소프트웨어는 접힘 및 정렬 제약 조건을 모두 도입하여 Sankoff 알고리즘의 제한된 버전을 구현하므로 프로세서와 메모리 사용량이 줄어들고 상용 하드웨어에서 더 큰 RNA 시퀀스를 분석할 수 있습니다.스템록은 2004년에 이안 홈즈에 의해 쓰여졌다.

Stemloc은 DART 소프트웨어 패키지의 일부로 다운로드할 수 있습니다.FASTA 또는 스톡홀름 형식의 입력 파일을 받을 수 있습니다.

용어.

• 접힘: RNA 접힘은 RNA 분자가 분자 내 상호작용을 통해 2차 구조를 획득하는 과정입니다.
• 봉투 접기:알고리즘에서 고려할 후보 접기 세트
• 얼라인먼트 엔벨로프:알고리즘에서 고려할 후보 정렬 세트

배경

1985년 David Sankoff가 이전에 개발한 알고리즘은 동적 프로그래밍을 사용하여 여러 RNA 구조를 동시에 정렬하고 예측합니다.Sankoff 알고리즘은 길이$L{\displaystyle }$(\$displaystyle$ L$)$의 $시퀀스$ O$(\displaystyle$ O$(L^{3N$${\displaystyle {}^{}}$와$O{\displaystyle (\backslash }$$displaystyle$ O$(L^{2N$$})$에서 $각각{\displaystyle }$ 시간과 공간이 소요됩니다.따라서 이는 동기부여적으로 $비용$이 많이 듭니다.스템록 같아Stemloc의 초기 목표는 확률적 문맥 자유 문법(SCFG) 점수 체계를 사용하고 Sankoff 알고리즘의 제한된 버전을 구현하여 두 RNA 시퀀스의 동시 정렬 및 구조 예측의 시간과 공간 비용을 줄이는 것이었다.

Stemloc는 얼라인먼트 봉투와 접이식 봉투를 사용하여 비교되는 시퀀스의 얼라인먼트와 2차 구조를 동시에 구속합니다.접이식 봉투를 사용하여 2차 구조에 대한 검색을 "제거"하고 알고리즘에서 고려할 수 있는 두 개의 RNA 시퀀스의 후속을 결정할 수 있습니다.예를 들어 특정 질소 결합 염기 쌍을 포함하거나 제외한다.얼라인먼트 봉투는 얼라인먼트 상에서 검색을 "절단"하고 두 시퀀스의 얼라인먼트에서 가능한 "컷포인트"를 결정하는 데 사용할 수 있습니다.예를 들어, 특정 잔류 수준 호몰로지를 포함하거나 제외합니다.접이식 봉투는 배열별로 개별적으로 미리 계산되며, 2차 구조를 무시한 채 두 배열을 비교하여 얼라인먼트 봉투가 미리 계산된다.글로벌 얼라인먼트와 로컬 얼라인먼트가 모두 지원됩니다.

입력

Stemloc의 입력은 FASTA 또는 스톡홀름 형식일 수 있습니다(각 항목에 대한 설명은 위 참조).입력 예는 다음과 같습니다.

stemloc --local dynalign.trna

"--local" 명령은 로컬 정렬 모드에서 파일을 분석합니다."--global"을 사용하면 전역 정렬 모드가 사용됩니다.

산출량

이 출력은 스톡홀름 형식입니다.시퀀스 이름, 일치 좌표, 얼라인먼트, 컨센서스 프라이머리 시퀀스, 각 시퀀스의 세컨더리 구조, 컨센서스 세컨더리 구조 및 얼라인먼트의 로그오디스코어(비트)가 표시됩니다."//" 줄은 정렬을 구분하거나 파일의 끝을 나타내는 데 사용됩니다.출력 예는 다음과 같습니다.

# 스톡홀름 1.0 #=GR RD0260/26-67 SS..<<<<......>>>>..(<<<......)>>>>>) RD0260/26-67 UACUCCUGACGGAGAUGUCCUCCUCCUCCUCCUCCUC #=UACUCCUCCUCCUCCUCCUC #=UACUCCUCCUCCUCCUC..CCCUGACG..GGA..GGUUC.AAUCC..C RD0500/26-66 UACGACUGUCGUGA-CGGGUCCAUCCCC #=GR RD0500/26-66 SS..<<<<......>>>...-.<<<......>>> #=SS_cons..<<<<......>>>>..<<<<......>>> #=GF SC 31.872 //

과정

스템로크는 알고리즘에 대한 점수 체계로 볼 수 있는 확률적 문맥 자유 문법에 크게 의존한다.Sankoff 알고리즘은 가능한 모든 접힘과 가능한 모든 정렬을 고려하기 때문에 매우 정확하고 정밀하지만 결과나 출력을 얻기 위해서는 상당한 시간이 걸립니다.이를 개선하기 위해 Stemloc는 사용자가 고려해야 할 총 접힘 및 정렬 수를 제한할 수 있도록 합니다.보다 구체적으로 각 시퀀스는 O${\displaystyle ({L\mathrm{}}^{}}$3$)({$$Displaystyle$ O$(L$$^{3})$ 시간$$ 내에 $개별적$으로 접고 O$(L$2)$$시간$$ $내$에 2차 구조를 무시하고 사전 정렬할 수 있습니다.예를 들어, 아래의 "-fast" 명령을 사용하면 가능한 모든 접힘을 분석하지 않고 최적의 100개의 RNA 구조만 고려됩니다."-log DOTPLOT" 명령을 사용하면 접힘 및 정렬 봉투의 시각적 표현이 출력됩니다.

stemloc nanos-tiny.rna - fast - log DOTPLOT

봉투의 구속

Stemloc의 주요 아이디어는 봉투를 만들기 위해 샘플링되는 접힘과 정렬의 수에 대한 임계값을 설정하는 것입니다.이 작업은 고려할 접힘 및 정렬 수를 설정하는 "-nf" 및 "-na" 옵션을 사용하여 수행할 수 있습니다.(-1을 사용하면 샘플링된 접힘 및 정렬 수가 제한되지 않으므로 두 파라미터에 모두 -1을 사용하면 입력 데이터 세트에서 Sankoff 알고리즘이 실행됩니다.

스템로크 나노스텐 -1 - na - 1

파라미터 트레이닝

Stemloc의 또 다른 특징은 데이터에서 확률론적 문맥이 없는 문법과 같은 확률론적 모델을 매개 변수화하는 능력이다.Stemloc는 Inside-Outside 알고리즘과 확률적 문맥 자유 문법을 사용하여 교육 세트의 가능성을 극대화한다.이것은 Stemloc에 대한 기본 매개변수가 Rfam(데이터베이스) 버전 5.0에서 30%와 40% 사이의 시퀀스 ID의 쌍별 정렬에 대해 훈련되었기 때문에 유용하다.단, 이들 파라미터가 항상 유효한 것은 아니기 때문에 사용자로서 파라미터를 트레이닝할 수 있는 것이 도움이 됩니다.

실제로

스템로크는 이후 RNA 구조 분석의 다양한 연구 출판물에 사용되어 왔다.특히 최적의 다중 시퀀스 정렬에 대한 연구에서 두드러집니다.

레퍼런스

• Holmes I. (2005) RNA 구조 진화의 가속 확률론적 추론.BMC 바이오 인포매틱스2005년 3월 24일; 6:73
• Sankoff D.(1985) RNA 접힘, 정렬 및 프로토시퀀스 문제의 동시 해결.SIAM 응용 수학 저널1985년 10월 45분 5초Sankoff D.(1985) RNA 접힘, 정렬 및 프로토시퀀스 문제의 동시 해결.SIAM 응용 수학 저널1985년 10월 45분 5초

외부 링크

• Stemloc 홈페이지 및 튜토리얼