테이레시아스 알고리즘

Teiresias 알고리즘은 생물학적 배열에서 단단한 패턴(모티프)을 발견하기 위한 조합 알고리즘입니다.그것은 그리스 예언자 테이레시아스의 이름을 따서 지어졌으며 1997년 이시도레 리구토스와 아리스 플로라토스에 ^[1]의해 만들어졌다.

관련된 단백질 또는 유전자의 1차 구조에서 배열 유사성을 찾는 문제는 생물학적 배열 분석에서 발생한다.일반적인 형식의 패턴 검출은 ^[2]NP-hard임을 알 수 있습니다.Teiresias 알고리즘은 패턴이 여러 위치에 걸쳐 있고 입력에 정확히 k번 나타나면 패턴의 모든 fragment(서브 패턴)가 입력에 k번 이상 표시되어야 한다는 관찰에 기초하고 있습니다.이 알고리즘은 지정된 입력에 사용자 정의 복사본 수가 있는 모든 패턴을 생성할 수 있으며 전체 공간의 열거를 방지하여 매우 효율적으로 관리할 수 있습니다.마지막으로, 알고리즘은 길이와 구성 모두에서 최대인 모티브를 보고한다.

Teiresias 알고리즘의 새로운 구현은 최근 Thomas Jefferson 대학의 Computational Medicine Center에 의해 제공되었습니다.Teiresias는 또한 같은 센터의 인터랙티브 웹 기반 사용자 인터페이스를 통해 액세스할 수 있습니다.양쪽의 외부 링크를 참조해 주세요.

패턴 설명

Teiresias 알고리즘은 정규 표현을 사용하여 패턴을 정의합니다.이를 통해 각 위치에 나타나는 문자(리터럴)뿐만 아니라 특정 문자 그룹(브래치 포함 리터럴) 또는 임의의 문자(와일드 카드)에서 보고된 패턴을 구성할 수 있습니다.알고리즘에 의해 작성된 패턴은 입력에 적어도k개의 인스턴스가 있는 <L,W> 패턴입니다.여기서 L w W 、 L 、 W 、 k의 양의 정수입니다.패턴은 L개의 연속 리터럴 또는 괄호로 묶은 리터럴이 최대 W 위치에 걸쳐 있는 경우에만 <L, W> 패턴이라고 불립니다(즉, W-L 와일드 카드보다 많은 것은 사용할 수 없습니다).

알고리즘은 최대 패턴만 보고합니다.일련의 시퀀스 S가 주어졌을 때, S에 k번 나타나는 패턴 P는 P'보다 특이하고 S에 정확히 k번 나타나는 패턴 P'가 존재하지 않는 경우에만 최대라고 한다.이러한 패턴 P'가 존재하면 P는 최대가 될 수 없으며 P는 P'에 포함되는 것으로 간주한다.패턴 P'는 (a)와일드카드를 역참조하거나 (b)괄호 리터럴에 괄호 리터럴을 인스턴스화하거나 (c)P, 괄호 리터럴의 오른쪽에 일련의 리터럴, 괄호 리터럴 또는/또는 와일드카드를 부가하거나 (d) 리터럴의 문자열 또는 리터럴의 선두에 부가함으로써 P'를 얻을 수 있는 경우에만 패턴 P'보다 특이하다고 한다.P의 ^[3]왼쪽에 있는 ild cards.

알고리즘 설명

Teiresias는 스캔과 컨볼루션의 두 단계로 구성됩니다.첫 번째 단계에서는 입력이 최소 요구 사항인 기본 패턴을 충족하는 패턴을 스캔합니다.기본 패턴은 정확히 L 리터럴 및/또는 괄호로 묶인 리터럴로 구성되며, 최대 W-L 와일드 카드를 포함합니다.컨볼루션 중에 기본 패턴이 재귀적으로 결합되어 최대 패턴이 생성된다.컨볼루션이 실행되는 순서는 모든 패턴이 생성되고 모든 최대 패턴이 그것들에 의해 포함된 모든 패턴보다 먼저 생성된다는 것을 보증하기 때문에 매우 중요합니다.순서는 다음 규칙에 의해 지정됩니다.

• 각 패턴의 priority는 왼쪽에서 오른쪽으로 내용에 따라 정의됩니다.
• 리터럴은 괄호로 묶은 리터럴보다 높은 priority를 가지며 둘 다 와일드카드보다 높은 priority를 가집니다(구체적인 우선).
• 패턴이 길수록 우선순위가 높아집니다.
• 동점은 알파벳 순으로 해결됩니다.

모든 최대 패턴이 먼저 생성된다는 보증을 고려할 때, 새로 생성된 패턴을 모든 최대 패턴과 비교하여 확인하고 잠재되어 있는지 확인하는 것이 쉬우며, 이 경우 해당 패턴은 폐기됩니다.새로 작성한 패턴이 서브셋되지 않으면 최대 패턴 목록에 추가됩니다.패턴을 조합하여 새로운 최대 패턴을 형성할 수 없는 경우 알고리즘은 종료됩니다.최대 패턴의 길이는 가장 긴 입력 시퀀스의 길이로 위에서부터 제한됩니다.

시간의 복잡성

이 알고리즘은 「출력에 민감」합니다.TEIESIAS 알고리즘의^[3] 시간 복잡도는 다음과 같습니다.

$\ displaystyle O\left(W^{L}m\log m+(C^{m}+t_{H)\sum _{P_{max}}{rc(P)}\right}$

L 및 W는 패턴의 "최소 밀도"을 정의하는 사용자 지정 매개 변수인 경우, 입력의 입력의 수를 포함할 수 없습니다. value, summary σ 、컨볼루션 중에 확장용 패턴을 유지하는 스택에 배치되는 패턴의 최대 수입니다.

외부 링크

• 알고리즘의 C++ 베이스의 실장은, 여기서 확인할 수 있습니다.
• Teiresias의 대화형 웹 기반 사용자 인터페이스는 여기에서 찾을 수 있습니다.

레퍼런스