소개

이 기사는 DNA 서열의 정렬을 반환하는 엑셀 함수에 대한 기사입니다.

Needleman-Wunsch에 의한 알고리즘에 의한 정렬이므로 함수명은 nwa()로 했습니다.

정책

궁극적으로 만드는 함수는

그렇다면 다음과 같은 정렬을 반환하는 함수입니다.


엑셀 시트에서 알고리즘을 표시한 후 함수를 작성합니다.

엑셀 시트에서 알고리즘 확인

두 개의 행렬을 준비합니다. 정렬하고 싶은 2개의 DNA 서열의 길이를 m과 n으로 하면, 세로 m x 가로 n의 크기의 행렬입니다. 행렬은 점수 행렬과 추적 백 행렬입니다. 초기 상태는 다음과 같습니다.

두 개의 DNA 서열은 한 글자씩 구분하여 셀에 넣고 행과 열의 레이블로 사용합니다.

점수 행렬

초기 상태를 다음과 같이 합니다.

추적 백 행렬

초기 상태를 다음과 같이 합니다.

행렬을 채우는 방법

일정한 규칙에 따라 행렬을 왼쪽 위에서 채웁니다. 규칙은 다음과 같습니다.
지금부터 채우려는 셀의 번지를 x, y로 했을 때, 이하의 3개의 스코어 중, 가장 높은 스코어를 셀(x, y)의 값으로 한다(2개 이상이 같은 값으로, 최고치 될 수도 있다).

셀에 대응하는 염기가 동일한 경우(셀의 열 라벨과 행 라벨을 비교해 같은 경우), 셀(x-1, y-1)의 값에 1을 더한 값, 그렇지 않은 경우 , 셀 (x-1, y-1)의 값에서 1을 뺀 값

셀 (x-1, y)의 값에서 1을 뺀 값

셀 (x, y-1)의 값에서 1을 뺀 값

즉, 셀(x-1, y-1)은 왼쪽 상단 셀이고 셀(x-1,y)은 왼쪽 셀이고 셀(x, y-1)은 위 셀입니다.
또 이때, 트레이스백 행렬의 대응하는 셀에도 값을 넣습니다. 규칙은

최고 점수를 보여준 것이 '1'이면 LEFTUP

최고 점수를 보여준 것이 '2'라면 LEFT

최고 스코어를 나타낸 것이 「3」이라면, UP,
합니다.

엑셀상에서는, 이런 식으로 됩니다. MAX는 인수 중에서 최대값을 반환하는 함수입니다. 나중에 복사 붙여 넣기 위해 절대 참조를 사용합니다.

이쪽은 조금 까다 롭습니다.


그리고는 만든 식을 복사 붙여넣어 행렬을 채웁니다.


추적 백 행렬의 오른쪽 하단 셀에서 기록한대로 거슬러 올라갑니다. LEFTUP라고 쓰면 왼쪽 상단으로 날아간다고 합니다. 추적 된 셀의 배경을 빨간색으로 두었습니다.



이제 두 개의 배열을 어떻게 나란히 할 수 있는지 알게 되었지만,이 행렬을 기반으로 VBA를 사용하지 않고 정렬을 만드는 것은 어렵 기 때문에 이후 VBA에서 함수를 만듭니다.

VBA 코드

알고리즘만 알고 버리면, 특히 어려운 곳은 없네요. 여기에서는 2차원 행렬 대신 1차원 행렬을 사용합니다. 폭 n의 행렬 좌표(x, y)는 1차원 행렬에서 index가 $x + n*y$가 됩니다.

'DNA配列を2つ受け取ります。DNAXとDNAYとします。

Public Function nwa(DNAX As String, DNAY As String) As String

Dim n As Integer
Dim m As Integer
Dim u As Integer
Dim l As Integer
Dim ul As Integer
Dim score As Integer
Dim alignmentX As String
Dim alignmentY As String
Dim alignmentLine As String

alignmentX = ""
alignmentY = ""
alignmentLine = ""
n = Len(DNAX)
m = Len(DNAY)

Dim scm() As Integer 'スコアマトリックスscm
Dim trm() As String 'トレースバックマトリックス trm
ReDim scm(0 To n * m)
ReDim trm(0 To n * m)


'マトリックスの初期化
For K = 1 To n - 1
    scm(K) = -2 * K
    trm(K) = "LEFT"
Next K

For J = 1 To m - 1
    scm(J * n) = -2 * J
    trm(J * n) = "UP"
Next J

'規則従って2つのマトリックスを埋める
For Y = 1 To m - 1
    For X = 1 To n - 1
        u = scm(X + (Y - 1) * n) - 1
        l = scm(X - 1 + Y * n) - 1
        If Mid(DNAX, X, 1) = Mid(DNAY, Y, 1) Then
            ul = scm(X - 1 + (Y - 1) * n) + 1
            Else
            ul = scm(X - 1 + (Y - 1) * n) - 1
        End If

        If ul >= u And ul >= l Then
                scm(X + Y * n) = ul
                trm(X + Y * n) = "LEFTUP"
        ElseIf u >= ul And u >= l Then
                scm(X + Y * n) = u
                trm(X + Y * n) = "UP"
        ElseIf l >= ul And l >= u Then
                scm(X + Y * n) = l
                trm(X + Y * n) = "LEFT"
        End If
    Next X
Next Y


'スコア算出と、アラインメントの作成
'アラインメントの各行を別々に作って最後に足し合わせる。
'ギャップ部分は - を挿入
score = 0
X = n - 1
Y = m - 1
While X <> 0 Or Y <> 0
        q = trm(X + Y * n)
        If q = "LEFT" Then
            alignmentX = Mid(DNAX, X, 1) & alignmentX
            alignmentY = "-" & alignmentY
            alignmentLine = " " & alignmentLine
            X = X - 1
        ElseIf q = "UP" Then
           alignmentX = "-" & alignmentX
            alignmentY = Mid(DNAY, Y, 1) & alignmentY
            alignmentLine = " " & alignmentLine
            Y = Y - 1
        ElseIf q = "LEFTUP" Then
            If Mid(DNAX, X, 1) = Mid(DNAY, Y, 1) Then
                score = score + 1
                alignmentLine = "|" & alignmentLine
                Else
                alignmentLine = " " & alignmentLine
            End If
            alignmentX = Mid(DNAX, X, 1) & alignmentX
            alignmentY = Mid(DNAY, Y, 1) & alignmentY
            X = X - 1
            Y = Y - 1
        End If
Wend

'VBA関数の作り方のルールに従って、最後に関数名=返り値とする。
nwa = alignmentX & vbNewLine & alignmentLine & vbNewLine & alignmentY
End Function

끝에

마지막으로 score를 돌려주도록(듯이) 변경하면, 그러한 사용법도 할 수 있네요.

이전에 만든 함수이지만 여기에서 공개하기로 결정했습니다. 한때 읽었던 책에 있던 해설을 좀처럼 이해하지 못하고 번뇌한 적이 있습니다. 여기서 기사가 고민하는 사람을 이해하는 데 도움이 되길 바랍니다.