1.

Dynamic programming은 전산학의 알고리즘 중의 한 유형으로, 일단 가장 간단한 해답을 알고 있고, 그 해답을 이용해 점점 더 전체로 확장 시켜 나가면서 마지막 대답을 얻는 경우에 이용되는 알고리즘이다. 즉 가장 간단한 s와 t의 첫 번째 서열의 적절한 배열에 대한 해답을 쉽게 알 수 있고, 그 값을 근거로 하여 해답을 점점 확장 시켜 전체 서열의 적절한 배열을 구하는 것이다.

여기서 s와 t를 각각 행렬의 축으로 하고 unit cost model(일치=0, 치환, 삽입, 삭제=1)을 적용하여 각각의 행렬의 항들을 채워나가면 다음과 같은 행렬을 만들 수 있다.

오른쪽 그림은 거리 행렬 (distance matrix)에서 최소값을 나타내는 행로를 표시 한 것이다. 서열 s에 대하여 대각선은 일치 혹은 치환을, 수평선은 삽입을, 수직선을 삭제를 나타낸다.
대각선에 의해 표시된 행로에 의해 s와 t를 배열하면 다음과 같다.

때때로 적절한 배열을 위한 최소한의 행로는 단 한 개가 아니고 여러 개가 될 수 있다.

Dynamic Programming을 이용하여 임의의 서열과 데이터 베이스에 저장된 서열들을 비교하는 방법을 Smith-Waterman 알고리즘이라 한다. 현재 이 알고리즘을 이용하여 유사성 검색 서비스를 제공하는 곳은 EBI의 BLITZ와 Bic-sw Database Searches가 있고 Weizmann Institute of Science의 BIOCCELERATOR는 전자 우편을 통해 결과를 제공하는 서비스를 한다.

Smith-Waterman 알고리즘을 이용한 검색 프로그램으로 EBI에서 제공하는 Bic-sw Database Searches가 있다. 서비스 페이지 (http://www2.ebi.ac.uk/Bic-sw/)에 가서 서열을 입력하면 WEB 혹은 e-mail을 통해 검색 결과를 보내준다. Bic-sw는 interactive access를 요구해도 일이 바쁘면 자동적으로 전자 우편으로 보내주기 때문에 access mode에 관계없이 반드시 전자 우편 주소를 기입해야 한다.

YOUR EMAIL : 검색 결과를 받기 위한 전자 우편 주소를 입력하는 곳
SEARCH TITLE : 검색 제목을 적는 곳
RESULT: 결과를 바로 볼 것인가 전자 우편을 통해 받을 것인가를 정하는 곳
DATABASE : Bic-sw는 다음의 데이터 베이스를 제공한다.

swall	non-redundant protein database
Swissprot	SWISS-PROT protein database
Swnew	updated to SWISS-PROT
Trembl	TREMBL ( Translated EMBL)
Tremblnew	TREMBLNEW (Translated EMBL updates)
Swall	SWISS-PROT + TREMBL + SWISSNEW + TREMBLENEW

GAPWEIGHT : 배열을 할 때 첫 번째 생기는 gap에 대한 감점을 정하는 곳으로 기본값은 15이다.
LENWEIGHT : 배열을 할 때 연속적으로 생기는 gap에 대한 감점을 정하는 곳이다. 기본값은 1이다.
QUERYGAP : 입력한 서열에서 첫 번째 생기는 gap에 대한 감점을 정할 수 있다.
QUERYLEN : 입력한 서열에서 연속적으로 생기는 gap에 대한 감점을 정할 수 있다.
MATRIX : 측정 행렬을 정할 수 있다. 기본값은 BLOSUM62이다.
SHOW NUMBER OF ALIGNMENTS : 결과 출력파일에서 배열해서 보여주는 서열들의 수를 정할 수 있다.
SHOW NUMBER OF SCORES : 결과 출력 파일에서 상위 몇 개까지의 score를 보여주는 가를 정할 수 있다.
LOWEST Z-SCORE MIN LIST TO REPORT : z-score가 지정한 값 이상이 되는 list만 보여주게 정할 수 있다.
SHOW MINIMUM QUALITY SCORE : 출력 파일에 쓰여지는 결과의 minimum quality를 정할 수 있다.
NORMALISATION TYPE : Z score를 길이에 따라 normalization 하는 방법을 정할 수 있다. LOG는 logarithmic normalization을 의미하고 z-score와 E-value를 알고 싶으면 stat를 선택한다. 기본값은 normalization을 하지 않는 것이다.
DO AVERAGING OF SCORES : Sequence composition에 따른 quality score를 조정할 수 있는 곳이다.
ORDER OUTPUT BY OVERLAPS QUALITY : overlap option을 주면 결과에서 alignment할 때 overlap이 생기는 부분에 감점을 주게 된다.