가장 가까운 문자열

이론 컴퓨터 과학에서 가장 가까운 문자열은 입력 문자열 집합의 기하학적 중심을 찾으려는 ^[1]NP-하드 연산 문제다.

'중심'이라는 단어를 이해하기 위해서는 두 문자열 사이의 거리를 정의할 필요가 있다.보통 해밍 거리를 염두에 두고 이 문제를 연구한다.

형식 정의

보다 공식적으로, n length-m 문자열 s₁, s₂, ..., s를_n 고려할 때, 가장 가까운 문자열 문제는 모든 i에 대해 d(s,s_i) ≤ k와 같은 새로운 length-m 문자열을 추구하며, 여기서 d는 해밍 거리를 나타내고 k는 가능한 한 작다.^[2]가장 가까운 문자열 문제의 의사결정 문제 버전인 NP-완전성은 대신 k를 다른 입력으로 받아들여 모든 입력 문자열의 Hamming 거리 k 내에 문자열이 있는지 여부를 질문한다.^[1]

가장 가까운 끈 문제는 해밍 거리를 사용하여 원소 사이의 거리를 측정하는 일반적인 1-중심 문제의 특별한 경우로 볼 수 있다.

동기

생물정보학에서 가장 가까운 끈 문제는 DNA에서 신호를 찾는 문제에 대해 집중적으로 연구된 측면이다.

단순화 및 데이터 감소

가장 가까운 문자열의 인스턴스에는 문제에 필수적이지 않은 정보가 포함될 수 있다.어떤 의미에서 가장 가까운 문자열의 일반적인 입력은 문제의 경도에 기여하지 않는 정보를 포함한다.예를 들어, 일부 문자열이 a 문자를 포함하지만 z 문자를 포함하는 문자열이 없는 경우 z로 모든 것을 대체하면 본질적으로 동등한 인스턴스(즉, 수정된 인스턴스의 솔루션에서 원래 솔루션을 복원할 수 있으며, 그 반대의 경우도 마찬가지임)를 산출할 수정한 인스턴스의 솔루션에서 원래 솔루션을 복원할 수 있다.

입력 정상화

같은 길이를 공유하는 모든 입력 문자열이 서로 위에 쓰여지면 행렬이 형성된다.특정 행 유형은 본질적으로 솔루션에 대해 동일한 의미를 갖는다.예를 들어, 열을 항목(a, a, a, b)으로 대체하면 다른 열(x, x, y)으로 이어질 수 있지만, 두 열 모두 동일한 구조인 viz. 처음 두 항목이 동일하지만 세 번째 항목과 다르기 때문에 해결 가능성에 영향을 줄 수는 없다.

입력 인스턴스는 각 열에서 가장 자주 발생하는 문자를 a로, 두 번째로 자주 발생하는 문자를 b로 교체하여 정규화할 수 있다.정규화된 인스턴스에 대한 해결책이 주어진 경우, 솔루션 문자를 모든 열의 원래 버전으로 다시 매핑하면 원본 인스턴스를 찾을 수 있다.

열의 순서는 문제의 경도에 기여하지 않는다.즉, 특정 순열 π에 따라 모든 입력 문자열을 허용하고 수정된 인스턴스(instance)에 대해 솔루션 문자열 s를 얻는다면 π은⁻¹ 원래 인스턴스에 대한 해결책이 될 것이다.

예

입력 문자열 ubwx, shuwv, xvwu가 세 개 있는 인스턴스.이것은 다음과 같은 매트릭스로 쓰일 수 있다.

u	v	w	x
x	u	w	v
x	v	w	u

첫 번째 열에는 값(u, x, x)이 있다.x는 가장 자주 등장하는 캐릭터인 만큼 a로 대체하고, 두 번째로 자주 등장하는 u를 b로 대체해 새로운 첫 번째 컬럼(b, a, a)을 얻는다.두 번째 열에는 값이 있다(v, u, v).첫 번째 열의 경우, v는 a로, u는 b로 대체되어 새로운 두 번째 열(a, b, a)을 얻는다.모든 열에 동일한 작업을 수행하면 표준화된 인스턴스가 제공됨

b	a	a	a
a	b	a	b
a	a	a	c

정규화를 통해 얻은 데이터 감소

입력을 정상화하면 알파벳 크기가 최대 입력 문자열 수로 줄어든다.이는 실행 시간이 알파벳 크기에 따라 달라지는 알고리즘에 유용할 수 있다.

근사성

리 외숨겨진 상수가 크기 때문에 사실상 사용할 수 없는 다항식 시간 근사 방법을^[3] 발전시켰다.

고정-모수 추적성

가장 가까운 문자열은 $O{\displaystyle (k}$ ${\displaystyle L}$+ ${\displaystyle k}$ ${\displaystyle {}^{}}$ ${\displaystyle \cdot }$ ${\displaystyle d^{}}$ )${\displaystyle O(kL+kd\cdot$ d$^{d})$로 풀 수 있으며$,$ 여기서 k는 입력 문자열의 수, L은 모든 문자열의 길이, d는 솔루션 문자열에서 임의의 입력 문자열까지의 원하는 최대 거리이다.^[4]

다른 문제와의 관계

가장 가까운 문자열은 더 일반적인 가장 가까운 하위 문자열 문제의 특별한 경우로서, 이것은 엄격히 더 어렵다.가장 가까운 문자열은 여러 가지 면에서 고정 파라미터로 판명되지만, 가장 가까운 하위 문자열은 이러한 파라미터와 관련하여 W[1]-hard이다.

참조