Feng-Doolittle algorithm
Progressive alignment algorithm by Feng and Doolittle (1987)
Basic idea
1. Calculate diagonal matrix of N(N 1) distances between all pairs of N
Copyright By PowCoder代写 加微信 powcoder
sequences.
2. Construct guide tree using UPGMA4 on the distance matrix from step 1. 3. Build the alignment in the order defined by the guide tree – from the leaves
towards the root.
3.1 Starting from the first internal node added to the tree, align the child
nodes (which may be two sequences, a sequence and an alignment, or
two alignments).
3.2 Repeat previous step for all other internal nodes in the order that
they were added to the tree, until all sequences have been aligned.
4or some other clustering algorithm
Feng-Doolittle algorithm: distances
The pairwise sequence distances are found by aligning each pair and recording a normalized
d(A,B)= logSe↵ = log Sobs Srand
Sobs the score of aligning sequences A and B as obtained by DP for PSA;
Smax is the average score Sobs(A,A)+Sobs(B,B)’ 2
Srand is the expected score for an alignment of the pair when the residues are randomly shu✏ed.
Se↵ is roughly a normalized percentage similarity which decays exponentially towards zero with increasing evolutionary distance.
Taking log(Se↵ ) converts the normalized score into an approximate distance that gets larger approximately linearly with evolutionary distance.
Feng-Doolittle method: aligning sequence to MSA
A sequence is aligned to an MSA by aligning it to each sequence in the MSA and choosing the highest scoring alignment.
Best pairwise alignment determines alignment to group
Feng-Doolittle method: aligning sequence to MSA
Best pairwise alignment determines alignment to group
Feng-Doolittle method: aligning sequence to MSA
—- determines alignment to group
This column encouraged because it has no cost
Best pairwise alignment
Feng-Doolittle method: aligning sequence to MSA
—- Best pairwise alignment
determines alignment to group
Feng-Doolittle method: aligning sequence to MSA
After alignment is completed, gap symbols are replaced with a character X which can be aligned to any other character (gap or residue) with no cost. Makes gaps align with each other.
Best pairwise alignment determines alignment to group
Feng-Doolittle method: aligning MSA to MSA
Group alignment determined by best pairwise alignment between groups
Feng-Doolittle method: aligning MSA to MSA
Group alignment determined by best pairwise alignment between groups
Feng-Doolittle method: aligning MSA to MSA
Group alignment determined by best pairwise alignment between groups
Feng-Doolittle method: aligning MSA to MSA
—- —- —- —-
Group alignment determined by best pairwise alignment between groups
Feng-Doolittle method: aligning MSA to MSA
Group alignment determined by best pairwise alignment between groups
—- —- —-
Feng-Doolittle method: aligning MSA to MSA
Group alignment determined by best pairwise alignment between groups
Progressive mis-alignment
Progressive mis-alignment
Quality depends on the initial pairwise alignments; errors propagate; “frozen” subalignments; 55 / 64
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com