환형문자열은 문자열의 첫 글자와 마지막 글자가 연결되어 고리 모양을 이루는 문자열로서 자연계에서 박테리아나 미토콘드리아의 DNA 등에서 흔히 발견된다. 다중서열배치 문제는 주어진 문자열 집합에서 유사한 부분을 중심으로 모든 문자열을 배치하는 문제로 분자 생물학 및 생물 정보학에서 여러 가지 연구에 응용되는 중요한 문제이다. 본 논문에서는 환형문자열에 대하여 해빙거리 기반의 쌍합 목적함수를 최소화하는 다중서열배치 문제를 정의한다. 또한 이를 해결하는 두 가지 알고리즘을 제안한다.
Circular strings are different from linear strings in that the first (leftmost) symbol of a circular string is wrapped around next to the last (rightmost) symbol. In nature, for example, bacterial and mitochondrial DNAs typically form circular strings. In this paper, we consider the problem of multiple sequence alignment on circular strings, which is defined by using Hamming distance and Sum-of-Pairs score. We also propose two algorithms to solve this problem.
