我想制作一个多序列比对程序，通常是三个或更多相似长度序列的比对。 [英] i want to make a multiple sequence alignment program generally the alignment of three or more sequence of similar length.
问题描述
我知道如何进行多序列比对，但我不知道我将如何制作动态输入数量
这里是我的2 seq代码我需要算法帮助或输入超过2的东西
i know how to make multiple sequence alignment but i don't know how i'm gonna make it for dynamic number of inputs
here is my code of 2 seq i need help by algorithm or something to make the input more than 2
namespace DNA_Sequence_Alignment_Using_Dynamic_Programming_
{
//Coding By Sara El-Sayed El-Metwally @ Monday,19-12-2011, 9:00 pm
// Teaching Assistant ,Mansoura University ,Eygpt
class Cell
{
private Cell Prevoius_Cell;
private List<Cell> PreviousCells = new List<Cell>();
private int row;
private int Column;
private int Score;
private PrevcellType PCType;
public Cell()
{
}
public Cell(int row, int Col)
{
this.Column = Col;
this.row = row;
}
public enum PrevcellType { Left, Above, Diagonal };
public Cell(int row, int Col, int sco)
{
this.Column = Col;
this.row = row;
this.Score = sco;
}
public Cell(int row, int Col, int sco, Cell Prev)
{
this.Column = Col;
this.row = row;
this.Score = sco;
this.Prevoius_Cell = Prev;
}
public Cell(int row, int Col, int sco, Cell Prev, PrevcellType PType)
{
this.Column = Col;
this.row = row;
this.Score = sco;
this.Prevoius_Cell = Prev;
this.PCType = PType;
}
public Cell CellPointer
{
set { this.Prevoius_Cell = value; }
get { return this.Prevoius_Cell; }
}
public List<Cell> PrevCellPointer
{
set { this.PreviousCells = value; }
get { return this.PreviousCells; }
}
public Cell this[int index]
{
set { this.PreviousCells[index] = value; }
get { return this.PreviousCells[index]; }
}
public int CellScore
{
set { this.Score = value; }
get { return this.Score; }
}
public int CellRow
{
set { this.row = value; }
get { return this.row; }
}
public int CellColumn
{
set { this.Column = value; }
get { return this.Column; }
}
public PrevcellType Type
{
set { this.PCType = value; }
get { return this.PCType; }
}
}
}
class DynamicProgramming
{
public static Cell [，] Intialization_Step（字符串Seq1，字符串Seq2，int Sim，int NonSimilar，int Gap）
{
int M = Seq1.Length; //长度+ 1 // - AAA
int N = Seq2.Length; //长度+ 1 // - AAA
Cell [，] Matrix = new Cell [N，M];
//初始化第一行，Gap Penality等于i * Gap
for（int i = 0; i< Matrix.GetLength（1）; i ++）
{
Matrix [0，i] =新单元格（0，i，i * Gap）;
}
//初始化第一列有差距，等于i * Gap
for（int i = 0;我< Matrix.GetLength（0）; i ++）
{
Matrix [i，0] = new Cell（i，0，i * Gap）;
}
//每个单元格的填充矩阵具有方法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）;
< br $>
}
}
返回Matrix;
}
public static Cell Get_Max（int i，int j，string Seq1，string Seq2，Cell [，] Matrix，int相似，int NonSimilar，int GapPenality）
{
Cell Temp = new Cell（）;
int Sim;
int Gap = GapPenality;
if（Seq1 [i] == Seq2 [j]）
Sim =类似;
其他
Sim = NonSimilar;
int M1，M2，M3;
M1 = Matrix [j - 1，i - 1] .CellScore + Sim;
M2 =矩阵[j，i - 1] .CellScore + Gap;
M3 =矩阵[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）; }
}
}
返回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 =新列表< char>（）;
Cell CurrentCell = Matrix [Sq2.Length - 1，Sq1.Length - 1];
而（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.C ellRow]）;
}
CurrentCell = CurrentCell.CellPointer;
}
}
}
公共部分类Form1：表格
{
public Form1（）
{
InitializeComponent（）;
}
private void button1_Click（object sender，EventArgs e ）
{
//保持对齐的列表
List< char> SeqAlign1 = new List< char>（）;
List< char> SeqAlign2 =新列表< char>（）;
this.richTextBox1.Clear（）;
//每个序列以 - 开头管理动态编程表来说明原因？在datagridview单元格中显示表格[0,0]
string Seq1 = - + this.textBox1.Text;
string Seq2 = - + this.textBox2 .Text;
//获取对齐参数
//相似度的比例
int Sim = int.Parse（this.textBox3.Text ）;
//非相似性的比例
int NonSim = int.Parse（this.textBox4.Text）;
//规模差距（Gap Penality）
int Gap = int.Parse（this.textBox5.Text）;
//字符串Seq1 = - GAATTCAGTTA;
//字符串Seq2 = - GGATCGA;
//准备用于计算最佳对齐的矩阵
Cell [，] Matrix = DynamicProgramming.Intialization_Step（Seq1，Seq2 ，Sim，NonSim，Gap）;
//准备Datagridview以显示动态编程矩阵的结果
this.dataGridView1.ColumnCount = Matri x.GetLength（1）+1;
for（int i = 0;我< this.dataGridView1.ColumnCount; i ++）
{
this.dataGridView1.Columns [i] .Width = 25; // 18为正值
}
this.dataGridView1.RowHeadersWidth = 25;
this.dataGridView1.ColumnHeadersHeight = 25;
this.dataGridView1.RowCount = Matrix.GetLength（0）+1;
// for（int j = 1; j< Matrix.GetLength（0）+ 1; j ++）
/ / {
// this.dataGridView1.Rows [j] .HeaderCell.Value = Seq2 [j - 1];
//}
for（int j = 1; j< Matrix.GetLength（0）+1; j ++）
{
this.dataGridView1.Rows [j] .Cells [0] .Value = Seq2 [j-1];
}
for（int i = 1; i< Matrix.GetLength（1）+1; i ++）
{
this.dataGridView1.Rows [0] .Cells [i] .Value = Seq1 [i-1];
//this.dataGridView1.Columns[i].HeaderText = Seq1 [i-1] .ToString（）;
}
for（int j = 1; j< Matrix.GetLength（0）+1; j ++）
{
for（int i = 1; i< Matrix.GetLength（1）+1; i ++）
{
this.dataGridView1.Rows [j] .Cells [i] .Value = Matrix [j-1，i-1] .CellScore;
}
}
//从最终单元格追溯矩阵，其中包含最大分数{从结束单元格[SeqAlign2.Count - 1，SeqAlign1.Count - 1]到初始单元格[0,0]}
DynamicProgramming。 Traceback_Step（Matrix，Seq1，Seq2，SeqAlign1，SeqAlign2）;
//显示对齐结果
//记下矩阵中的迹线反向完成（追溯）
for（int j = SeqAlign1.Count - 1; j> = 0; j--）
{
this.richTextBox1.AppendText（SeqAlign1 [j] .ToString（））;
}
this.richTextBox1.AppendText（'\ n'.ToString（））;
for（int f = SeqAlign2.Count - 1; f> = 0; f--）
{
this.richTextBox1.AppendText（SeqAlign2 [f] .ToString（））;
}
}
private void richTextBox1_TextChanged（object sender，EventArgs e）
{
}
private void label2_Click（object sender，EventArgs e）
{
}
private void Form1_Load（object sender，EventArgs e）
{
//默认值
this.textBox1.Text =GAATTCAGTTA;
this.textBox2.Text =GGATCGA;
this.textBox3.Text =1;
this.textBox4.Text = - 1;
this.textBox5.Text = - 2;
}
}
class DynamicProgramming
{
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 Penality 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 Penality 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;
}
}
}
public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
}
private void button1_Click(object sender, EventArgs e)
{
// Lists That Holds Alignments
List<char> SeqAlign1 = new List<char>();
List<char> SeqAlign2 = new List<char>();
this.richTextBox1.Clear();
// Each sequence begin with - to manage dynamic programming table to show why?? show the table in datagridview cell[0,0]
string Seq1 = "-"+this.textBox1.Text;
string Seq2 = "-"+this.textBox2.Text;
// get parameters of alignment
// scale of Similarity
int Sim = int.Parse(this.textBox3.Text);
// scale of non Similarity
int NonSim = int.Parse(this.textBox4.Text);
// Scale of gap(Gap Penality)
int Gap= int.Parse(this.textBox5.Text);
//string Seq1 = "-GAATTCAGTTA";
//string Seq2 = "-GGATCGA";
//prepare Matrix for Computing optimal alignment
Cell[,] Matrix = DynamicProgramming.Intialization_Step(Seq1, Seq2,Sim,NonSim,Gap);
// prepare Datagridview to show result of Dynamic Programming Matrix
this.dataGridView1.ColumnCount = Matrix.GetLength(1)+1;
for (int i = 0; i < this.dataGridView1.ColumnCount; i++)
{
this.dataGridView1.Columns[i].Width = 25;//18 for positive values
}
this.dataGridView1.RowHeadersWidth = 25;
this.dataGridView1.ColumnHeadersHeight = 25;
this.dataGridView1.RowCount = Matrix.GetLength(0)+1;
//for (int j = 1; j < Matrix.GetLength(0) + 1; j++)
//{
// this.dataGridView1.Rows[j].HeaderCell.Value= Seq2[j - 1];
//}
for (int j = 1; j < Matrix.GetLength(0)+1; j++)
{
this.dataGridView1.Rows[j].Cells[0].Value = Seq2[j-1];
}
for (int i = 1; i < Matrix.GetLength(1)+1; i++)
{
this.dataGridView1.Rows[0].Cells[i].Value = Seq1[i-1];
//this.dataGridView1.Columns[i].HeaderText = Seq1[i-1].ToString();
}
for (int j = 1; j < Matrix.GetLength(0)+1; j++)
{
for (int i = 1; i < Matrix.GetLength(1)+1; i++)
{
this.dataGridView1.Rows[j].Cells[i].Value = Matrix[j-1, i-1].CellScore;
}
}
// Trace back matrix from end cell that contains max score { from end cell [SeqAlign2.Count - 1,SeqAlign1.Count - 1] to initial cell [0,0]}
DynamicProgramming.Traceback_Step(Matrix, Seq1, Seq2,SeqAlign1,SeqAlign2);
// Display Result of alignments
//note the trace in matrix done in reverse manner (trace back)
for (int j = SeqAlign1.Count - 1; j >= 0; j--)
{
this.richTextBox1.AppendText(SeqAlign1[j].ToString());
}
this.richTextBox1.AppendText('\n'.ToString());
for (int f = SeqAlign2.Count - 1; f >= 0; f--)
{
this.richTextBox1.AppendText(SeqAlign2[f].ToString());
}
}
private void richTextBox1_TextChanged(object sender, EventArgs e)
{
}
private void label2_Click(object sender, EventArgs e)
{
}
private void Form1_Load(object sender, EventArgs e)
{
// Default Values
this.textBox1.Text = "GAATTCAGTTA";
this.textBox2.Text = "GGATCGA";
this.textBox3.Text = "1";
this.textBox4.Text = "-1";
this.textBox5.Text = "-2";
}
}
推荐答案
我有点想法得到你，也就是说，如果你的代码完美地运行Seq1和Seq2，如果你想要第三个序列也可以工作，首先你可以将它们放在算法的循环中，用于Seq1和Seq2。然后你可以测试Seq2和Seq3。最后的Seq1和Seq3。
例如，Seq1，AACT; Seq2，AT; Seq3，CT;
在检查S1和S2时，它将是S1 =AACT而S2 = - AT
检查S2和S3，它将是S2 = - AT和S3 = - CT
在检查S1和S3时，它将是S1 =AACT并且S3 = - CT
我对得分知之甚少所以我不会写这篇文章。
A little idea I have got for you, which is, if your code works perfectly Seq1 and Seq2 and if you want a 3rd Sequence to work as well, first you could put them in a loop of the algo for Seq1 and Seq2. Then you could test Seq2 and Seq3. Last Seq1 and Seq3.
e.g, Seq1, "AACT"; Seq2, "AT"; Seq3, "CT";
On check S1 and S2, it will be S1="AACT" and S2="-A-T"
On check S2 and S3, it will be S2="-A-T" and S3="--CT"
On check S1 and S3, it will be S1="AACT" and S3="--CT"
I have little knowledge on scoring so I will not be writing about it.
这篇关于我想制作一个多序列比对程序，通常是三个或更多相似长度序列的比对。的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
