indels 만 사용하는 전역 다중 시퀀스 정렬 알고리즘

Question

여러 줄의 코드를 정렬하는 Sublime Text 스크립트를 작성하고 있습니다. 스크립트는 각 줄을 가져 와서 미리 정의 된 구분 기호 집합 (,;:=)으로 분할하고 동일한 너비로 패딩 된 '열'의 각 세그먼트와 다시 결합합니다. 이것은 모든 행에 동일한 구분자 세트가있을 때 잘 작동하지만 일부 행에는 여분의 세그먼트, 끝에 선택적 쉼표 등이있을 수 있습니다.

제 아이디어는 구분 기호의 표준 목록을 제안하는 것입니다. 특히, 구분자 문자열이 여러 개인 경우 주어진 문자열 중에서 삽입을 사용하여 결속 할 수있는 가장 짧은 문자열을 찾고 싶습니다. 몇 가지 연구를 한 후에, 이것이 불일치, 일치 및 indels가 없다는 것을 제외하고는 이것이 글로벌 다중 서열 정렬의 잘 알려진 문제점이라는 것을 알게되었습니다.

동적 프로그래밍 방식은 불행히도 적어도 일반적인 경우에는 문자열 수에 지수 적입니다. 불일치가 허용되지 않는 경우 더 빠른 솔루션에 대한 희망이 있습니까?

Answer 1

나는 불일치가 허용되지 않는 경우에도 그러한 희망이 없다는 담요 성명서를 작성하는 것을 주저하지만, 나는이 없다고 확신한다. 이유가 여기 있습니다.

시퀀스 정렬을 수행 할 때 생성되는 동적 프로그래밍 테이블의 크기는 대략 (문자열 길이)^(문자열 수)이므로 지수 런타임/공간 요구 사항입니다. 당신이 여기에 두 개의 문자열, ABC 및 ACB, 길이이 우리에게 3 × 3 테이블을 제공 3. 각과의 예입니다, 출처의 느낌을주고 :

A B C 
    A 0 1 2 
    C 1 1 1 
    B 2 1 2 

우리는 왼쪽 상단에서 시작하여이 테이블을 초기화 거기에서부터 오른쪽 아래로 나아가고 있어요. 테이블의 모든 위치에 도달하는 데 드는 총 비용은 해당 위치의 번호에 의해 부여됩니다 (간단히하기 위해 삽입, 삭제 및 대체에 모두 비용이 1 인 것으로 가정합니다). 주어진 위치에 도달하기 위해 사용 된 작업은 이전 값에서 이동 한 방향에 의해 제공됩니다. 오른쪽으로 이동한다는 것은 맨 위 문자열에서 요소를 삽입한다는 것을 의미합니다. 아래로 이동하면 옆쪽 문자열에서 요소를 삽입합니다. 대각선으로 이동한다는 것은 요소를 위아래에서 정렬한다는 의미입니다. 이러한 요소가 일치하지 않으면 대체를 나타내며 거기에 도달하기 위해 비용이 증가합니다.

그리고 그게 문제입니다. 불일치가 허용되지 않는다고해도 테이블의 길이와 높이 (삽입/삭제)를 담당하는 작업을 배제하지 않습니다. 더욱이 불일치를 허용하지 않는다고해도 잠재적 인 가능성은 배제되지 않습니다. 테이블의 대각선 운동은 때때로 가능합니다. 두 요소가 일치하지 않는 경우가 아닙니다. 또한 요소가 일치하는지 확인해야하므로 기본적으로 여전히 이동을 고려하고 있습니다. 따라서 최악의 경우 시간을 개선 할 수 없어야하며 평균 또는 최악의 경우에도 상당한 영향을 미치지 않을 것입니다.

밝은면에서 이것은 생물 정보학에서 매우 중요한 문제이므로 사람들은 몇 가지 해결책을 생각해 냈습니다. 그들은 결함이 있지만 귀하의 경우에 충분히 잘 작동 할 수 있습니다 (특히 문자열이 4 글자로 구성되어 있지 않다면 DNA보다 가짜 배열을 가질 확률이 적기 때문에 특히 그렇습니다) 알파벳). 그래서 은 Star Alignment와 Neighbor Joining을 살펴 봅니다.