具有一组字符而不是一个字符的序列比对算法 [英] Sequence Alignment Algorithm with a group of characters instead of one character
问题描述
摘要：
我从对齐算法的一些细节开始，最后，我问我一个问题。如果您了解对齐算法，请从头开始。
I'm beginning with some details about alignment algorithms, and at the end, I ask my question. If you know about alignment algorithm pass the beginning.
考虑一下，我们有两个字符串，例如：
Consider we have two strings like:
ACCGAATCGA
ACCGGTATTAAC
有一些算法，例如：史密斯-沃特曼或 Needleman–Wunsch ，将这两个序列对齐并创建一个矩阵。看看以下部分的结果：
There is some algorithms like: Smith-Waterman Or Needleman–Wunsch, that align this two sequence and create a matrix. take a look at the result in the following section:
Smith-Waterman Matrix
§ § A C C G A A T C G A
§ 0 0 0 0 0 0 0 0 0 0 0
A 0 4 0 0 0 4 4 0 0 0 4
C 0 0 13 9 4 0 4 3 9 4 0
C 0 0 9 22 17 12 7 3 12 7 4
G 0 0 4 17 28 23 18 13 8 18 13
G 0 0 0 12 23 28 23 18 13 14 18
T 0 0 0 7 18 23 28 28 23 18 14
A 0 4 0 2 13 22 27 28 28 23 22
T 0 0 3 0 8 17 22 32 27 26 23
T 0 0 0 2 3 12 17 27 31 26 26
A 0 4 0 0 2 7 16 22 27 31 30
A 0 4 4 0 0 6 11 17 22 27 35
C 0 0 13 13 8 3 6 12 26 22 30
Optimal Alignments
A C C G A - A T C G A
A C C G G A A T T A A
问题：
我的问题很简单，但答案也许很简单看起来并不容易。我想使用一组字符作为单个字符，例如： [A0] [C0] [A1] [B1] 。但是在这些算法中，我们必须使用单个字符。
My question is simple, but maybe the answer is not easy as it looks. I want to use a group of character as a single one like: [A0][C0][A1][B1]. But in these algorithms, we have to use individual characters. How can we achieve that?
P.S。考虑我们有以下顺序： #read #write #add #write 。然后将其转换为类似的内容：#read到A .... #write到B .... #add到C。然后我的序列变为： ABCB 。但是我有很多以＃开头的单词。而且ASCII表不足以转换所有这些表。然后，我需要更多字符。唯一的方法是为每个单词使用 [A0] ... [Z9] 之类的东西。或使用数字。
P.S. Consider we have this sequence: #read #write #add #write. Then I convert this to something like that: #read to A .... #write to B.... #add to C. Then my sequence become to: ABCB. But I have a lot of different words that start with #. And the ASCII table is not enough to convert all of them. Then I need more characters. the only way is to use something like [A0] ... [Z9] for each word. OR to use numbers.
PS：此链接
PS：有另一篇帖子，它想要类似的内容，但我想要的却有所不同。在这个问题中，我们有一组字符，它们以 [开头，以] 结尾。无需使用 ee 这样的语义就等于 i 。
P.S: there is another post that want something like that, but what I want is different. In this question, we have a group of character that begins with a [ and ends with ]. And no need to use semantic like ee is equal to i.
推荐答案
假设我们有一个包含字母序列的日志文件。就像您说的一样，我将序列转换为 A0A1 ... 。例如，如果存在类似 #read #write #add #add #write 的序列，它将转换为 A0A1A2A1 。每次，我都读取两个字符并进行比较，但是像以前一样保留分数矩阵。这是我在C＃中用于史密斯-沃特曼字符串对齐的代码。 >
请注意， Cell 是用户定义的类。
Imagine we have a log file with alphabetic sequences. Like something you said, I converted sequences to A0A1... . For example, if there was a sequence like #read #write #add #write, it converted to A0A1A2A1. Every time, I read two character and compare them but keep score matrix like before. Here is my code in C# for smith-waterman string alignment.
Notice that Cell is a user defined class.
private void alignment()
{
string strSeq1;
string strSeq2;
string strTemp1;
string strTemp2;
scoreMatrix = new int[Log.Length, Log.Length];
// Lists That Holds Alignments
List<char> SeqAlign1 = new List<char>();
List<char> SeqAlign2 = new List<char>();
for (int i = 0; i<Log.Length; i++ )
{
for (int j=i+1 ; j<Log.Length; j++)
{
strSeq1 = "--" + logFile.Sequence(i);
strSeq2 = "--" + logFile.Sequence(j);
//prepare Matrix for Computing optimal alignment
Cell[,] Matrix = DynamicProgramming.Intialization_Step(strSeq1, strSeq2, intSim, intNonsim, intGap);
// Trace back matrix from end cell that contains max score
DynamicProgramming.Traceback_Step(Matrix, strSeq1, strSeq2, SeqAlign1, SeqAlign2);
this.scoreMatrix[i, j] = DynamicProgramming.intMaxScore;
strTemp1 = Reverse(string.Join("", SeqAlign1));
strTemp2 = Reverse(string.Join("", SeqAlign2));
}
}
}
class DynamicProgramming
{
public static Cell[,] Intialization_Step(string Seq1, string Seq2,int Sim,int NonSimilar,int Gap)
{
int M = Seq1.Length / 2 ;//Length+1//-AAA //Changed: /2
int N = Seq2.Length / 2 ;//Length+1//-AAA
Cell[,] Matrix = new Cell[N, M];
//Intialize the first Row With Gap Penality Equal To Zero
for (int i = 0; i < Matrix.GetLength(1); i++)
{
Matrix[0, i] = new Cell(0, i, 0);
}
//Intialize the first Column With Gap Penality Equal To Zero
for (int i = 0; i < Matrix.GetLength(0); i++)
{
Matrix[i, 0] = new Cell(i, 0, 0);
}
// 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 intDiagonal_score;
int intUp_Score;
int intLeft_Score;
int Gap = GapPenality;
//string temp1, temp2;
//temp1 = Seq1[i*2].ToString() + Seq1[i*2 + 1]; temp2 = Seq2[j*2] + Seq2[j*2 + 1].ToString();
if ((Seq1[i * 2] + Seq1[i * 2 + 1]) == (Seq2[j * 2] + Seq2[j * 2 + 1])) //Changed: +
{
intDiagonal_score = Matrix[j - 1, i - 1].CellScore + Similar;
}
else
{
intDiagonal_score = Matrix[j - 1, i - 1].CellScore + NonSimilar;
}
//Calculate gap score
intUp_Score = Matrix[j - 1, i].CellScore + GapPenality;
intLeft_Score = Matrix[j, i - 1].CellScore + GapPenality;
if (intDiagonal_score<=0 && intUp_Score<=0 && intLeft_Score <= 0)
{
return Temp = new Cell(j, i, 0);
}
if (intDiagonal_score >= intUp_Score)
{
if (intDiagonal_score>= intLeft_Score)
{
Temp = new Cell(j, i, intDiagonal_score, Matrix[j - 1, i - 1], Cell.PrevcellType.Diagonal);
}
else
{
Temp = new Cell(j, i, intDiagonal_score, Matrix[j , i - 1], Cell.PrevcellType.Left);
}
}
else
{
if (intUp_Score >= intLeft_Score)
{
Temp = new Cell(j, i, intDiagonal_score, Matrix[j - 1, i], Cell.PrevcellType.Above);
}
else
{
Temp = new Cell(j, i, intDiagonal_score, Matrix[j , i - 1], Cell.PrevcellType.Left);
}
}
if (MaxScore.CellScore <= Temp.CellScore)
{
MaxScore = Temp;
}
return Temp;
}
public static void Traceback_Step(Cell[,] Matrix, string Sq1, string Sq2, List<char> Seq1, List<char> Seq2)
{
intMaxScore = MaxScore.CellScore;
while (MaxScore.CellPointer != null)
{
if (MaxScore.Type == Cell.PrevcellType.Diagonal)
{
Seq1.Add(Sq1[MaxScore.CellColumn * 2 + 1]); //Changed: All of the following lines with *2 and +1
Seq1.Add(Sq1[MaxScore.CellColumn * 2]);
Seq2.Add(Sq2[MaxScore.CellRow * 2 + 1]);
Seq2.Add(Sq2[MaxScore.CellRow * 2]);
}
if (MaxScore.Type == Cell.PrevcellType.Left)
{
Seq1.Add(Sq1[MaxScore.CellColumn * 2 + 1]);
Seq1.Add(Sq1[MaxScore.CellColumn * 2]);
Seq2.Add('-');
}
if (MaxScore.Type == Cell.PrevcellType.Above)
{
Seq1.Add('-');
Seq2.Add(Sq2[MaxScore.CellRow * 2 + 1]);
Seq2.Add(Sq2[MaxScore.CellRow * 2]);
}
MaxScore = MaxScore.CellPointer;
}
}
}
这篇关于具有一组字符而不是一个字符的序列比对算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
