MUSCLE(얼라인먼트 소프트웨어)
MUSCLE (alignment software)| 원저작자 | 로버트 C.에드거 |
|---|---|
| 개발자 | 드라이브 5 |
| 초기 릴리즈 | 전( |
| 안정된 릴리스 | 3.8.31 / 2016년 8월 , 전( |
| 저장소 | github.com/rcedgar/muscle/releases/tag/v5.1 at GitHub |
| 운영 체제 | Linux, macOS, Windows |
| 플랫폼 | IA-32, x86-64 |
| 이용가능기간: | 영어 |
| 유형 | 다중 시퀀스 얼라인먼트 |
| 면허증. | 퍼블릭 도메인 |
| 웹 사이트 | drive5 |
MUSCLE(Multiple Sequence Comparison by Log-Expectation)은 단백질과 뉴클레오티드 배열의 다중 배열 정렬을 위한 컴퓨터 소프트웨어입니다.퍼블릭 도메인으로 라이선스가 부여되어 있습니다.그 방법은 로버트 C에 의해 출판되었다.2004년에 에드거가 두 신문에 실렸다.핵산 연구에 발표된 첫 번째 논문은 배열 정렬 알고리즘을 [1]소개했습니다.BMC 바이오인포매틱스에 게재된 두 번째 논문은 보다 기술적인 [2]세부사항을 제시하였다.
알고리즘.
MUSTLE 알고리즘은 드래프트 프로그레시브, 개량 프로그레시브 및 정제 단계의 세 단계로 진행됩니다.
스테이지 1: 드래프트 프로그레시브
이 첫 번째 단계에서 알고리즘은 정확도보다 속도를 강조하는 다중 정렬을 생성합니다.이 단계는 모든 입력 시퀀스의 쌍에 대한 k-mer 거리를 계산하여 거리 행렬을 작성하는 것으로 시작합니다.UPGMA는 거리 행렬을 군집화하여 이진 트리를 생성합니다.이 트리에서 트리의 각 잎에 대한 프로파일 작성부터 시작하여 프로그레시브 정렬이 구성됩니다.트리의 모든 노드에 대해 쌍방향 정렬이 2개의 자식 프로파일로 구성되어 해당 노드에 할당되는 새 프로파일이 생성됩니다.이것은 트리의 [1]루트에 있는 모든 입력 시퀀스의 다중 시퀀스 정렬이 있을 때까지 계속됩니다.
스테이지 2: 개량된 프로그레시브
이 스테이지에서는 1단계에서 얻은 다중 시퀀스 얼라인먼트를 사용하여 입력 시퀀스 쌍별로 키무라 거리를 계산하여 보다 최적의 트리를 얻는 데 중점을 두고 제2의 거리 매트릭스를 작성한다.UPGMA는 이 거리 행렬을 클러스터링하여 두 번째 이진 트리를 얻습니다.스테이지 1과 같이 프로그레시브 얼라인먼트를 실시하여 다중 시퀀스 얼라인먼트를 얻지만, 첫 번째 바이너리 트리에서 분기 순서가 변경된 서브트리의 얼라인먼트만을 계산함으로써 최적화되어 보다 정확한 [1]얼라인먼트를 얻을 수 있다.
스테이지 3: 개량
이 마지막 단계에서는 두 번째 트리에서 에지가 선택되며, 에지는 루트로부터 감소된 거리로 방문된다.선택한 가장자리가 삭제되고 트리가 두 개의 하위 트리로 분할됩니다.그런 다음 각 하위 트리에 대해 다중 정렬의 프로파일이 계산됩니다.서브트리 프로파일을 다시 정렬함으로써 새로운 다중 시퀀스 정렬이 생성됩니다.SP 점수가 향상되면 새 정렬이 유지되고 그렇지 않으면 폐기됩니다.에지를 삭제하고 정렬하는 프로세스는 컨버전스 [1]또는 사용자 정의 제한에 도달할 때까지 반복됩니다.
복잡성과 비교
알고리즘의 처음 두 단계에서는 시간 복잡도는 O(NL2 + NL2), 공간 복잡도는 O(N2 + NL + L2)입니다.정제 단계는 다른 용어인 O([1]NL)를3 시간 복잡성에 추가한다. MUSCLE은 일반적으로 (항상 그렇지는 않지만) 선택한 옵션에 따라 더 나은 시퀀스 정렬을 제공하기 때문에 종종 Clusteral을 대체하기 위해 사용된다.클러스터링보다 훨씬 빠릅니다. 더 큰 [1][2]선형일수록 더 빠릅니다.
알고리즘 흐름도
통합
MUSCLE은 DNASTAR의 Lasergene 소프트웨어, Genious 및 MacVector와 통합되어 있으며 Sequencher, MEGA, UGENE에서 플러그인으로 사용할 수 있습니다.MUSCLE은 또한 유럽 분자 생물학 연구소(EMBL)-유럽 생물 정보 연구소(EBI)[3]를 통해 웹 서비스로 이용할 수 있습니다.2016년 9월 현재, MUSCLE을 기술한 2개의 논문이 [4]총 19,000회 이상 인용되었습니다.
「 」를 참조해 주세요.
레퍼런스
- ^ a b c d e f Edgar RC (2004). "MUSCLE: multiple sequence alignment with high accuracy and high throughput". Nucleic Acids Research. 32 (5): 1792–97. doi:10.1093/nar/gkh340. PMC 390337. PMID 15034147.
- ^ a b Edgar RC (2004). "MUSCLE: a multiple sequence alignment method with reduced time and space complexity". BMC Bioinformatics. 5 (1): 113. doi:10.1186/1471-2105-5-113. PMC 517706. PMID 15318951.
- ^ "MUSCLE < Multiple Sequence Alignment < EMBL-EBI". Archived from the original on 18 January 2015. Retrieved 1 September 2014.
- ^ "Robert C. Edgar - Google Scholar Citations". Archived from the original on 24 September 2016. Retrieved 1 September 2016.
