Needleman Wunsch 알고리즘과 무차별 대항력은 어떻게 다릅니 까?

Question

Needleman-Wunsch 알고리즘의 결과를 정량화 할 수 있는지 궁금합니다 (일반적으로 뉴클레오타이드/단백질 서열을 정렬하는 데 사용됨).

고정 점수 체계와 가변 길이가 두 가지 연속 길이 인 S1 및 S2을 고려해보십시오. S1 및 S2의 가능한 모든 정렬을 무차별 대입으로 계산한다고 가정 할 때 가장 높은 점수를 매기는 점수는 x입니다. 물론 이것은 Needleman-Wunsch 방식보다 훨씬 복잡합니다.

Needleman-Wunsch 알고리즘을 사용하여 서열 정렬을 찾으려면 점수가 y이라고 말하십시오.

r은 두 개의 임의 시퀀스 R1 및 R2에 대해 Needleman-Wunsch를 통해 생성 된 점수라고 간주하십시오.

x은 (는) y과 비교하면 어떻습니까? y은 알려진 상 동성의 두 시퀀스에 대해 언제나 r보다 큽니까?

일반적으로 우리는 시퀀스 정렬 (대용량 접근 방식과 비교하여)을 상당히 빠르게하기 위해 Needleman-Wunsch 알고리즘을 사용하지만 함께 제공되는 정확도 비용 (있는 경우)을 이해하지 못한다는 것을 알고 있습니다. . 원래 종이 (Needleman & Wunsch, 1970)를 읽었지만 아직도이 질문이 남아 있습니다.

Answer 1

Needlman-Wunsch는 항상 최적의 대답을 산출합니다. 이는 무차별 적 힘보다 훨씬 빠르며 프로세스의 정확성을 희생하지 않습니다. 이것이 사용하는 핵심 통찰력은 가능한 모든 정렬을 생성하는 것이 실제로 필요하지 않다는 것입니다. 대부분의 정렬은 나쁜 하위 정렬을 포함하고 있기 때문에 최적 일 수는 없습니다. Needleman-Wunsch 알고리즘은 원래 가닥 조각에 대해 최적의 정렬을 천천히 구축 한 다음 최적 정렬이 약간 작은 경우 최적 정렬을 포함해야한다는 보장을 사용하여 더 작은 정렬을 더 큰 정렬로 천천히 성장시킵니다.

Answer 2

동적 프로그래밍이 최적의 솔루션 즉, y >= x이라는 보장을 찾는지 궁금합니다. 이에 대한 설명은 내가 나보다 가능성이 더 똑똑한 사람을 참조합니다 : 기본적으로

https://cs.stackexchange.com/questions/23599/how-is-dynamic-programming-different-from-brute-force

, 그것은 동적 프로그래밍 가능성, 즉 무력과 동일하지만 특정 문제에 대한 최적의 결과를 얻을 것이라고 말한다 최적의 벨만 원리를 만족하는.

https://en.wikipedia.org/wiki/Needleman%E2%80%93Wunsch_algorithm

특히 :

니들-분쉬 알고리즘이 여전히 널리 사용되는

니들-Wunsch에 대한 위키 백과 페이지에 따르면, 문제는 최적의 벨맨 원칙을 충족하지 최적의 글로벌 정렬을 위해, 특히 글로벌 정렬의 품질이 가장 중요 할 때 일 때.그러나 알고리즘은 두 시퀀스의 길이가 인 제품에 비례하여 시간과 공간에 대해 인 경우 값 비싸며 따라서 긴 시퀀스에는 적합하지 않습니다.

동일한 위키 백과 페이지의 다른 곳에서도 최적성에 대한 언급이 있습니다.