MUMUMMER

MUMmer

MUMMER는 시퀀스 정렬을 위한 생물정보학 소프트웨어 시스템이다.접미사 트리 데이터 구조를 기반으로 하며, 이 작업에 사용할 수 있는 가장 빠르고 효율적인 시스템 중 하나로, 매우 긴 시퀀스에 적용할 수 있다.그것은 서로 다른 게놈들을 비교하는데 널리 사용되어 왔다.최근 몇 년 동안, 그것은 게놈 조립을 서로 비교하는 데 인기 있는 알고리즘이 되었고, 이것은 과학자들이 더 많은 DNA 서열을 추가하거나 다른 게놈 조립 프로그램을 실행한 후에 게놈이 어떻게 변했는지 판단할 수 있게 해준다.'MUMMER'라는 약어는 'Maximal Unique Matchs' 즉 MUMs에서 유래한다.MUMMER 소프트웨어 패키지의 원래 알고리즘은 아트 델처, 사이먼 카시프, 스티븐 살츠버그가 설계했다.Mummer는 생물정보학에서 개발된 최초의 전체 게놈 비교 시스템이었다.이것은 원래 두 종류의 관련 박테리아를 비교하기 위해 적용되었다.

MUMMER 소프트웨어는 오픈 소스로 MUMMMER 홈페이지에서 확인할 수 있다.홈 페이지에는 시스템을 설명하는 기술 문서 링크도 있다.이 시스템은 주로 스티븐 살츠버그와 아서 델처 존스홉킨스 대학교 컴퓨터 생물학 센터에 의해 유지된다.

MUMMER은 과학 문헌에서 많이 인용된 생물정보학 시스템이다.구글 스콜라에 따르면 2013년 초 현재 원본 MUMMER 논문(Delcher et [1]al., 1999년)이 691회, MUMMER 2 논문(Delcher et al., 2002년)[2]이 455회, MUMMMER 3.0 기사(Kurtz et al., 2004년)[3]가 903회 인용됐다.

개요

MUMMER란 무엇인가?

원숭이와 어떤 관계인지 궁금하지 않으세요?만약 그렇다라고 답한다면, 나는 당신이 그 대답을 찾을 수 있는 알고리즘이 있다는 것을 말해줄 수 있다.만약 당신이 알고리즘 클래스를 가지고 있다면 (Wunch and Needleman에 의한) "Edit distance"가 떠오를 것이다; 이것은 이 같은 주제에 사용될 수 있다.그러나 "거리 편집" 알고리즘은 작은 시퀀스를 비교하기 위해 사용되며 게놈 정렬을 계산하는 데 오랜 시간이 걸릴 것이다.

게놈은 유기체(염색체 내)에 대한 유전적 지시/정보의 대열이다. 이제 "M과 같은 4Mb 시퀀스를 비교한다"고 상상해보자.다른 4Mb 시퀀스에 대한 결핵, 많은 알고리즘은 메모리가 부족하거나 완료하는 데 너무 오래 걸린다."(Arthur et al., 1999).[4]그 당시 4Mb의 메모리는 엄청난 것이었다. 그래서 그들은 이런 종류의 알고리즘을 만드는 것과 같은 것을 해야만 했다.연구원들은 게놈 서열을 비교하는 알고리즘을 만들어 왔다.Mummer는 게놈 전체의 빠른 정렬에 주로 사용되는 빠른 알고리즘이다.

MUMMER는 앞에서 언급한 바와 같이 빅 사이즈 시퀀스의 효율적인 정렬을 위한 시스템/프로세스로서, 이 알고리즘은 게놈 구조에 대한 발견을 위해 사용되어 왔다.알고리즘은 정말 잘 설계되어 있고 몇 초 안에 선형을 비교할 수 있다.이 알고리즘은 비교적 새롭기 때문에 이 알고리즘은 이전 알고리즘보다 1개 향상된 4가지 버전이 있다.

MUMMER 버전

MUMMER1

MUMMER1 또는 just MUMMER는 세 부분으로 구성되며, 첫 번째 부분은 접미사 나무 생성(MUM을 얻기 위해), 두 번째 부분은 가장 오래 증가하는 부분 또는 가장 긴 공통 부분(MUM을 주문하기 위해), 마지막으로 간격을 좁히기 위한 정렬로 구성된다.

이 과정을 시작하려면, 상기시키기 위해, 우리는 입력으로 두 개의 게놈을 얻어야 한다.일단 우리가 그것들을 받으면, 우리는 최대한의 독특한 매치(MUMs)를 찾을 것이다.MUMs의 알고리즘은 여러 가지 방법으로 할 수 있기 때문에 나름대로의 논리를 가지고 있다.예를 들어, nauve 알고리즘은 한 게놈의 모든 시퀀스를 거쳐 다른 게놈의 시퀀스와 비교하는데, 이는 m과 m2가 두 게놈인 O(m*m2)를 취한다.그러나 MUMMER는 빨라야 하기 때문에 O(m+m2)를 취하는 접미사 트리(Suffix tree)라는 데이터 구조를 이용한다.이 트리에서 MUM을 추출한다(두 시퀀스에 의해 하나의 내부 노드로 표현되는 부분).

일단 우리가 MOM을 식별하고 나면, 우리는 게놈을 선택하여 다른 게놈의 위치를 기준으로 MOM을 분류하고 제거해야 한다.이 단계는 게놈을 선택하고 노드(MUM)를 오름차순으로 열거하면 쉽게 할 수 있고, 다른 하나는 첫 번째 순서부터 노드에 따라 각 노드를 열거한다.즉, 위치에 관계없이 동일한 값의 MUM 한 쌍(두 게놈의 정확한 일치)을 열거한다.그런 다음 우리는 분류한다.이것을 실현하기 위해서, 우리는 이용 가능한 어떤 방법이라도 선택할 수 있다.예를 들어, Long Common Serpendence (Long Common Serpendence 문제) 또는 LIS(Long Increging Sepatence)를 사용하여 이 작업을 수행할 수 있다.이 프로세스가 끝나면 두 시퀀스의 MUM은 동일하게 정렬/순서가 지정된다(일부 MUM은 적은 숫자로 열거하기 전에 큰 숫자로 열거할 수 없기 때문에 현재로선 무시된다).이 단계의 가장 좋은 시간 복잡성은 O(nlogn)이다.

마지막으로, 우리는 MOM-Alignment 사이의 방해에 대처해야 하는데, 이것은 갭이라고 알려져 있을 수도 있다.우리는 이러한 공백을 메울 수 있는 다른 정렬 알고리즘을 사용한다.아서와 그의 팀(Arthur et al., 1999)은 다음과 같은 네 가지 등급에서 격차가 발생한다고 언급한다.[4]

  • SNP 간섭 – 두 시퀀스를 비교할 때 한 문자가 서로 달라진다.다시 말해, 그 등장인물의 앞과 뒤의 등장인물은 같을 것이다.
  • 삽입 – 두 시퀀스를 비교할 때 시퀀스 중 하나에만 나타나는 시퀀스가 있다.두 시퀀스를 비교하는 순간 다른 시퀀스의 빈 공백이 될 것이다.
  • 고도의 다형성 영역 – 두 개의 시퀀스를 비교할 때, 모든 문자가 서로 다른 연속성을 발견할 수 있다.
  • 반복 – 그것은 시퀀스의 반복이다.MOM은 오직 독특한 시퀀스만을 취할 수 있기 때문에, 그 간격은 MOM들 중 하나의 반복이 될 수 있다.

MUMMER 2

이 알고리즘은 더 적은 메모리를 요구하도록 재설계되었고, 프로세스는 첫 번째 알고리즘보다 더 빠르고 더 정확하다. 또한 더 큰 게놈 정렬을 허용한다.

개선된 것은 쿠르츠가 만든 접미사를 채용하여 접미사에 저장하는 양이었다.이 트리의 경우 한 시퀀스의 플러그 인에 불과하므로 삽입이 다르며, 다른 한 시퀀스는 비교가 더 많다(더하는 것과 같지만 우리는 그렇지 않다, 우리는 트리 안의 문자를 비교하고 있다).하나의 시퀀스를 저장하기 때문에 공간 복잡성을 줄인다.

마침내 첫 번째 MUMMER 알고리즘은 두 시퀀스만 맞추고 다른 단계로 뛰어올랐다.그러나, 더 나은 커버리지를 달성하기 위해, MUM의 시퀀스는 클러스터가 되고 있다(더 적은 수의 공백으로 분리된 MUM의 그룹이라는 의미).

MUMMER 3

Stefan Kurtz와 그의 동료들에 따르면, "MUMMER 3.0에서 가장 중요한 기술적 개선은 "접미사 트리의 공간 요구사항 감소"라는 글에서 설명한 트리의 콤팩트한 접미사-트리 표현에 기초하여 접미사-트리 코드를 완전히 다시 쓴 것이라고 한다.[6]

또 다른 개선점은 MOM의 이완이었다. 이는 이제 사용자는 모든 독특하지 않은 최대 일치 항목, 선택된 시퀀스에서만 고유한 모든 일치 항목 또는 원래의 MOM(두 시퀀스 모두에 고유한)을 찾을 수 있는 옵션을 갖게 되었다는 것을 의미한다.이것은 MUM의 복사본인 일부 누락된 부분을 피하기 위해 추가되었다.

MUMMER 4

기욤과 그의 팀에 따르면, 구현에 있어 약간의 추가적인 개선과 질의 병렬화를 통한 혁신도 있다고 한다.첫 번째, 그리고 가장 큰 개선점은 시험 중인 시퀀스의 크기 제한의 증가다.마지막으로, "MUMMER4는 이제 주어진 참조를 위해 접미사 배열을 저장하고 로드하는 옵션을 포함한다."(Marcais et al., 2018).[7]덕분에 접미사 트리는 한 번 만들고 저장된 접미사 트리에서 실행한 후 다시 만들 수 있다.

소프트웨어 - 오픈 소스

MUMMER는 오픈 소스 소프트웨어를 가지고 있다.이 패키지로 게임을 시작하는 가장 좋은 방법은 이 패키지의 웹사이트에 접속하는 것이다.

이 페이지는 오픈 소스, 설치 요건 및 단계, 패키지를 실행하는 프로세스 및 실행 시퀀스의 몇 가지 예에 대해 설명한다.이 웹사이트에 더 많은 정보가 있다.만약 당신이 갇히게 된다면, 그 웹사이트는 그 경우 누구에게 연락해야 할지에 대한 정보를 가지고 있다.이 페이지에는 이 알고리즘을 사용할 수 있는 귀중한 정보가 있다.

관련 항목

다른 유형의 시퀀스 정렬이 있으며, 관련 주제 중 일부는 다음과 같다.

  • 거리 편집
  • 블라스트
  • 보타이
  • BWA
  • 블라
  • 마우브
  • 라스트즈
  • 블라스트

참조

  1. ^ Delcher, A. L.; Kasif, S.; Fleischmann, R. D.; Peterson, J.; White, O.; Salzberg, S. L. (1999). "Alignment of whole genomes". Nucleic Acids Research. 27 (11): 2369–2376. doi:10.1093/nar/27.11.2369. PMC 148804. PMID 10325427.
  2. ^ Delcher, A. L.; Phillippy, A.; Carlton, J.; Salzberg, S. L. (2002). "Fast algorithms for large-scale genome alignment and comparison". Nucleic Acids Research. 30 (11): 2478–2483. doi:10.1093/nar/30.11.2478. PMC 117189. PMID 12034836.
  3. ^ Delcher, A.; Harmon, D.; Kasif, S.; White, O.; Salzberg, S. (1999). "Improved microbial gene identification with GLIMMER". Nucleic Acids Research. 27 (23): 4636–4641. doi:10.1093/nar/27.23.4636. PMC 148753. PMID 10556321.
  4. ^ a b Delcher, A.; Kasif, S.; Fleischmann, R.; Peterson, J.; White, O.; Salzberg, S. (1999). "Alignment of Whole Genomes". Nucleic Acids Research. 27 (11): 2369–2376. doi:10.1093/nar/27.23.4636. PMC 148804. PMID 10325427.
  5. ^ Kurtz, S.; Phillippy, A.; Delcher, A.; Smoot, M.; Shumway, M.; Antonescu, C.; Salzberg, S. (2004). "Versatile and open software for comparing large genomes" (PDF). Genome Biology. 5 (2): R12. doi:10.1186/gb-2004-5-2-r12. PMC 395750. PMID 14759262.
  6. ^ Kurtz, S. (1999). "Reducing the Space Requirement of Suffix Trees". Software: Practice and Experience. 29 (13): 1149–1171. doi:10.1002/(SICI)1097-024X(199911)29:13<1149::AID-SPE274>3.0.CO;2-O.
  7. ^ Marçais, Guillaume.; Pillippy, A.; Delcher, A.; Coston, R.; Salzberg, S.; Zimin, A. (2018). "MUMmer4: A fast and versatile genome alignment system". PLOS Computational Biology. 14 (1): e1005944. Bibcode:2018PLSCB..14E5944M. doi:10.1371/journal.pcbi.1005944. PMC 5802927. PMID 29373581.

외부 링크