다중 단백질 서열 정렬을 위한 새로운 무작위 반복 전략

다중 단백질 서열의 엄격한 정렬은 서열의 수가 적은 경우에도 비현실적이 됩니다. 이는 서열의 길이의 곱에 따라 컴퓨터 메모리와 시간 요구 사항이 증가하기 때문입니다. 우리는 이러한 최적 정렬에 접근하기 위한 전략을 고안하였으며, 이는 동적 프로그래밍의 집중적인 컴퓨터 저장소 및 시간 요구 사항을 수정합니다. 우리의 알고리즘은 정렬되지 않은 서열 그룹을 무작위로 두 개의 하위 그룹으로 나누고, 그 사이에서 Needleman-Wunsch 스타일의 알고리즘으로 최적 정렬을 얻습니다. 우리의 알고리즘은 두 개의 정렬된 서열 하위 그룹의 길이에 해당하는 차원을 가진 행렬을 사용합니다. 쌍 정렬 과정은 전체 그룹을 두 개의 하위 그룹으로 무작위로 나누어진 다른 조합을 사용하여 반복됩니다. 동적 프로그래밍을 통해 n차원 격자를 해결하는 엄격한 접근 방식과 비교할 때, 우리의 반복 알고리즘은 제한된 테스트 문제 집합에서 최적 솔루션과 일치하거나 근접한 정렬을 제공합니다. 우리는 이 알고리즘을 IBM PC 클래스의 기계에서 실행되는 컴퓨터 프로그램으로 구현하였으며, 사용자 친화적인 환경을 제공하여 서열 또는 서열 그룹을 동시에 또는 점진적으로 정렬하도록 선택할 수 있습니다.