Коллеги, добрый день. Есть пара вопросов, может кто пояснит.
Существует алгоритм для выравнивания последовательностей днк (в принципе любого текста) используемый в молекулярной биологии - Needleman–Wunsch algorithm. Ссылка на вики внизу. Там есть псевдокод. Переписал его в swift и разбираюсь в playground как он работает. Хочу добавить его как стандартную опцию в программе. Возник вопрос.
Кратко что происходит. Вначале заполняется двумерный массив числами. (Принцип расчета каждого числа для каждой позиции хорошо изложен в вики.) Затем происходит чтение данной таблицы с конца и этот процесс связан с внесением или не внесением gaps между characters. В итоге имеем две последовательности с gaps в определенных позициях и эти последовательности имеет максимально возможное количество совпадающие characters.
Вопрос .
Таблица с числами заполняемся так, что получаемое число может быть получено при суммировании как с одной соседней позицией так и с другой соседней позицией. Это влияет на то, что при чтении таблицы мы будем иметь не один, а например два варианта того как расположены gaps. Т.е. есть несколько вариантов выравнивания.
В коде ниже возможен только один вариант. Вопрос состоит в том как поменять код чтобы можно было получить все возможные варианты.
//penalty для совпадений (match), не совпадений (mismatch) и вставок-делеций(indel)
let match = 1
let mismatch = -1
let indel = -1
var string1 = "ATCATGGCTGATTTTTTTCG" // B
var string2 = "AATCTGCTGATGG" // A
//заполняем двумерный массив
var arrayOfArraysOfScoresSimilarities = [[Int]]()
for j in 0...string1.count
{
arrayOfArraysOfScoresSimilarities.append([-j])
}
for i in 1...string2.count
{
arrayOfArraysOfScoresSimilarities[0].append(-i)
}
var arrayOfString1 = Array(string1)
var arrayOfString2 = Array(string2)
for i in 0..<arrayOfString1.count // B
{
for j in 0..<arrayOfString2.count// A
{
var score = Int()
if arrayOfString1[i] == arrayOfString2[j]
{
score = [(arrayOfArraysOfScoresSimilarities[i][j] + match), (arrayOfArraysOfScoresSimilarities[i + 1][j] + indel), (arrayOfArraysOfScoresSimilarities[i][j + 1] + indel)].max()!
}
else if arrayOfString1[i] != arrayOfString2[j]
{
score = [(arrayOfArraysOfScoresSimilarities[i][j] + mismatch), (arrayOfArraysOfScoresSimilarities[i + 1][j] + indel), (arrayOfArraysOfScoresSimilarities[i][j + 1] + indel)].max()!
}
arrayOfArraysOfScoresSimilarities[i + 1].append(score)
}
}
arrayOfArraysOfScoresSimilarities //заполненный массив
//читаем массив с конца и получаем последовательности
var alignedString1 = ""
var alignedString2 = ""
arrayOfString1 = [Character("N")] + arrayOfString1
arrayOfString2 = [Character("N")] + arrayOfString2
var i = arrayOfString2.count - 1
var j = arrayOfString1.count - 1
while i > 0 || j > 0
{
if i > 0 && j > 0 && arrayOfArraysOfScoresSimilarities[j][i] == arrayOfArraysOfScoresSimilarities[j - 1][i - 1] + match
{
alignedString2 = String(arrayOfString2[i]) + alignedString2
alignedString1 = String(arrayOfString1[j]) + alignedString1
i = i - 1
j = j - 1
}
else if i > 0 && arrayOfArraysOfScoresSimilarities[j][i] == arrayOfArraysOfScoresSimilarities[j][i - 1] + indel
{
alignedString2 = String(arrayOfString2[i]) + alignedString2
alignedString1 = "-" + alignedString1
i = i - 1
}
else if j > 0 && arrayOfArraysOfScoresSimilarities[j][i] == arrayOfArraysOfScoresSimilarities[j - 1][i] + indel
{
alignedString2 = "-" + alignedString2
alignedString1 = String(arrayOfString1[j]) + alignedString1
j = j - 1
}
else if i > 0 && j > 0 && arrayOfArraysOfScoresSimilarities[j][i] == arrayOfArraysOfScoresSimilarities[j - 1][i - 1] + mismatch
{
alignedString2 = String(arrayOfString2[i]) + alignedString2
alignedString1 = String(arrayOfString1[j]) + alignedString1
i = i - 1
j = j - 1
}
}
//выровненные последовательности
alignedString1
alignedString2