www.swamiyer.net/cs110/project3.pdf Problem 2. (Recovering the Alignment) Now th
ID: 3722682 • Letter: W
Question
www.swamiyer.net/cs110/project3.pdf Problem 2. (Recovering the Alignment) Now that we know bow to compute the edit distance between two strings, we next want to recover the optimal aligument iteelf. The key idoa is to retrace the stepe of the dynamic programming algorithm backwards, re discovering the path of choices (highlighted in rod in the table above) from opt to) to) to opt 0O 03. To determine the choioe that lod to ope ta) tg], we consider the throe posibilitios: 1. The optimal alignment matches xta] up with a gap. In this case, we must have epeta-ope 130)2 2. The optimal alignment mathes , up with a gap. In this case, we must have optiuj)-opt tut + 1] + 2. 3. The optimal aligament matches [A] up with yt). In this case, we must have opt (41111 opeta 1+1 if x(1) equals 3), or optag opes 11 otherwise. Write a program lsaeat. py that reads from standard inpat, the output produced by otie distance.r, ie, input strings and y, and the opt matrix. The program should then recover an optimal alignment using the procedure described above, and write to standard output the edit distance between z and y and the alignmeut itself, using the following format The first line should contain the edit distance, preceded by the text Bait distaace-. Each subeequent lise should coutain a character from the first string, followed by the paired character from the second string, followed by the associated penalty. Use the duaracter e to indicate a gap in either string. 3 of 5 CS110 Project 3 (Global Sequence Alignment) Swami lyer s rthens edis aistance Py data/exsapleto.txt Ipyhon3 aligaest py Edit diataace ·7 ! c 2 TG1 cco CAIExplanation / Answer
/*(j-1,i-1) Diagonal Cell to entry (j,i)
(j-1,i) Above Cell to entry (j,i)
(j,i-1) Left Cell to entry (j,i)
j-1,i
j,i
j-1,i-1
j,i-1
*/
/*The first class contains three methods that describe the steps of dynamic programming algorithm. The first method is named Intialization_Step, this method prepares the matrix a[i,j] that holds the similarity between arbitrary prefixes of the two sequences. The algorithm starts with shorter prefixes and uses previously computed results to solve the problem for larger prefixes
The second method named Get_Max computes the value of the cell (j,i)
The third method is named Traceback_Step. This method will produce the alignment by traversing the cell matrix(N-1,M-1) back towards the initial entry of the cell matrix (1,1).
*/
public static Cell[,] Intialization_Step
(string Seq1, string Seq2,int Sim,int NonSimilar,int Gap)
{
int M = Seq1.Length;//Length+1//-AAA
int N = Seq2.Length;//Length+1//-AAA
Cell[,] Matrix = new Cell[N, M];
//Intialize the first Row With Gap Penalty Equal To i*Gap
for (int i = 0; i < Matrix.GetLength(1); i++)
{
Matrix[0, i] = new Cell(0, i, i*Gap);
}
//Intialize the first Column With Gap Penalty Equal To i*Gap
for (int i = 0; i < Matrix.GetLength(0); i++)
{
Matrix[i, 0] = new Cell(i, 0, i*Gap);
}
// Fill Matrix with each cell has a value result from method Get_Max
for (int j = 1; j < Matrix.GetLength(0); j++)
{
for (int i = 1; i < Matrix.GetLength(1); i++)
{
Matrix[j, i] = Get_Max(i, j, Seq1, Seq2, Matrix,Sim,NonSimilar,Gap);
}
}
return Matrix;
}
public static Cell Get_Max(int i, int j, string Seq1,
string Seq2, Cell[,] Matrix,int Similar,int NonSimilar,int GapPenality)
{
Cell Temp = new Cell();
int Sim;
int Gap = GapPenality;
if (Seq1[i] == Seq2[j])
Sim = Similar;
else
Sim = NonSimilar;
int M1, M2, M3;
M1 = Matrix[j - 1, i - 1].CellScore + Sim;
M2 = Matrix[j, i - 1].CellScore + Gap;
M3 = Matrix[j - 1, i].CellScore + Gap;
int max = M1 >= M2 ? M1 : M2;
int Mmax = M3 >= max ? M3 : max;
if (Mmax == M1)
{ Temp = new Cell(j, i, M1, Matrix[j - 1, i - 1],
Cell.PrevcellType.Diagonal); }
else
{
if (Mmax == M2)
{ Temp = new Cell(j, i, M2, Matrix[j, i - 1], Cell.PrevcellType.Left); }
else
{
if (Mmax == M3)
{ Temp = new Cell(j, i, M3, Matrix[j - 1, i],
Cell.PrevcellType.Above); }
}
}
return Temp;
}
public static void Traceback_Step(Cell[,] Matrix,
string Sq1, string Sq2, List<char> Seq1, List<char> Seq2)
{
//List<char> Seq1 = new List<char>();
//List<char> Seq2 = new List<char>();
Cell CurrentCell = Matrix[Sq2.Length - 1, Sq1.Length - 1];
while (CurrentCell.CellPointer != null)
{
if (CurrentCell.Type == Cell.PrevcellType.Diagonal)
{
Seq1.Add(Sq1[CurrentCell.CellColumn]);
Seq2.Add(Sq2[CurrentCell.CellRow]);
}
if (CurrentCell.Type == Cell.PrevcellType.Left)
{
Seq1.Add(Sq1[CurrentCell.CellColumn]);
Seq2.Add('-');
}
if (CurrentCell.Type == Cell.PrevcellType.Above)
{
Seq1.Add('-');
Seq2.Add(Sq2[CurrentCell.CellRow]);
}
CurrentCell = CurrentCell.CellPointer;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.