Локальное выравнивание между X и Y, по крайней мере, в одном столбце, выравнивающем C по W.
Имея две последовательности X длины n и Y длины m, мы ищем локальное выравнивание с наивысшей оценкой (т. е. выравнивание между подстрокой X' из X и подстрокой Y' из Y), которое имеет хотя бы один столбец в в котором C из X' выравнивается с W из Y' (если такое выравнивание существует). В качестве модели подсчета очков мы используем матрицу замещения s и линейные штрафы за пропуски с параметром d.
Напишите код для эффективного решения проблемы. Если вы используете динамическое программирование, достаточно указать уравнения для вычисления записей в матрицах динамического программирования и указать, где начинается и заканчивается трассировка.
Мое решение:
Я взял 2 последовательности, а именно «HCEA» и «HWEA», и попытался решить вопрос. Вот мой код. Выполнил ли я то, что задано в вопросе? Если я ошибаюсь, пожалуйста, скажите мне, где я ошибся, чтобы я изменил свой код.
И есть ли другой способ решить вопрос? Если он доступен, кто-нибудь может опубликовать псевдокод или алгоритм, чтобы я мог его кодировать.
public class Q1 {
public static void main(String[] args) {
// Input Protein Sequences
String seq1 = "HCEA";
String seq2 = "HWEA";
// Array to store the score
int[][] T = new int[seq1.length() + 1][seq2.length() + 1];
// initialize seq1
for (int i = 0; i <= seq1.length(); i++) {
T[i][0] = i;
}
// Initialize seq2
for (int i = 0; i <= seq2.length(); i++) {
T[0][i] = i;
}
// Compute the matrix score
for (int i = 1; i <= seq1.length(); i++) {
for (int j = 1; j <= seq2.length(); j++) {
if ((seq1.charAt(i - 1) == seq2.charAt(j - 1))
|| (seq1.charAt(i - 1) == 'C') && (seq2.charAt(j - 1) == 'W')) {
T[i][j] = T[i - 1][j - 1];
} else {
T[i][j] = Math.min(T[i - 1][j], T[i][j - 1]) + 1;
}
}
}
// Strings to store the aligned sequences
StringBuilder alignedSeq1 = new StringBuilder();
StringBuilder alignedSeq2 = new StringBuilder();
// Build for sequences 1 & 2 from the matrix score
for (int i = seq1.length(), j = seq2.length(); i > 0 || j > 0;) {
if (i > 0 && T[i][j] == T[i - 1][j] + 1) {
alignedSeq1.append(seq1.charAt(--i));
alignedSeq2.append("-");
} else if (j > 0 && T[i][j] == T[i][j - 1] + 1) {
alignedSeq2.append(seq2.charAt(--j));
alignedSeq1.append("-");
} else if (i > 0 && j > 0 && T[i][j] == T[i - 1][j - 1]) {
alignedSeq1.append(seq1.charAt(--i));
alignedSeq2.append(seq2.charAt(--j));
}
}
// Display the aligned sequence
System.out.println(alignedSeq1.reverse().toString());
System.out.println(alignedSeq2.reverse().toString());
}
}
@Shole Ниже приведены два вопроса и ответы, представленные в моем решенном листе.
- Выравнивание суффикса X с префиксом Y. Имея две последовательности X и Y, мы ищем выравнивание с наивысшей оценкой между любым суффиксом X и любым префиксом Y. В качестве модели оценки мы используем матрицу подстановки s и линейную Штрафы за пробел с параметром d. Приведите эффективный алгоритм для оптимального решения этой задачи за время O(nm), где n — длина X, а m — длина Y. Если вы используете подход динамического программирования, достаточно дать уравнения, необходимые для вычисления матрица динамического программирования, чтобы объяснить, какая информация хранится для обратной трассировки, и указать, где начинается и заканчивается трассировка.
Решение: пусть X_i будет префиксом X длины i, а Y_j обозначит префикс Y длины j. Мы вычисляем матрицу F так, что F[i][j] является лучшим результатом выравнивания любого суффикса X_i и строки Y_j. Мы также вычисляем матрицу трассировки P. Вычисление F и P можно выполнить за время O(nm) с использованием следующих уравнений:
F[0][0]=0
for i = 1..n: F[i][0]=0
for j = 1..m: F[0][j]=-j*d, P[0][j]=L
for i = 1..n, j = 1..m:
F[i][j] = max{ F[i-1][j-1]+s(X[i-1],Y[j-1]), F[i-1][j]-d, F[i][j-1]-d }
P[i][j] = D, T or L according to which of the three expressions above is the maximum
После того, как мы вычислили F и P, мы находим наибольшее значение в нижней строке матрицы F. Пусть F[n][j0] будет этим наибольшим значением. Мы начинаем трассировку с F[n][j0] и продолжаем трассировку, пока не достигнем первого столбца матрицы. Построенное таким образом выравнивание и есть решение.
- Выравнивание Y по подстроке X без пробелов в Y Имея строку X длины n и строку Y длины m, мы хотим вычислить выравнивание Y с наивысшей оценкой по любой подстроке X с дополнительным ограничением, которое мы не разрешается вставлять какие-либо пробелы в Y. Другими словами, вывод представляет собой выравнивание подстроки X' из X со строкой Y, так что оценка выравнивания является максимально возможной (среди всех вариантов X') и таким образом, чтобы выравнивание не вносило пробелов в Y (но могло вводить пробелы в X'). В качестве модели подсчета очков мы снова используем матрицу замещения s и линейные штрафы за пропуски с параметром d. Предложите эффективный алгоритм динамического программирования, который оптимально решает эту задачу за полиномиальное время. Достаточно привести уравнения, необходимые для вычисления матрицы динамического программирования, объяснить, какая информация сохраняется для трассировки, и указать, где трассировка начинается и заканчивается. Каково время работы вашего алгоритма?
Решение:
Пусть X_i будет префиксом X длины i, а Y_j обозначит префикс Y длины j. Мы вычисляем матрицу F так, что F[i][j] является лучшим результатом выравнивания любого суффикса X_i и строки Y_j, так что выравнивание не вставляет пробелов в Y. Мы также вычисляем матрицу трассировки P. Вычисление F и P может быть выполнено за время O(nm) с использованием следующих уравнений:
F[0][0]=0
for i = 1..n: F[i][0]=0
for j = 1..m: F[0][j]=-j*d, P[0][j]=L
for i = 1..n, j = 1..m:
F[i][j] = max{ F[i-1][j-1]+s(X[i-1],Y[j-1]), F[i][j-1]-d }
P[i][j] = D or L according to which of the two expressions above is the maximum
После того, как мы вычислили F и P, мы находим наибольшее значение в крайнем правом столбце матрицы F. Пусть F[i0][m] будет этим наибольшим значением. Мы начинаем трассировку с F[i0][m] и продолжаем трассировку, пока не достигнем первого столбца матрицы. Построенное таким образом выравнивание и есть решение.
Надеюсь, вы получили некоторое представление о том, что мне действительно нужно.
