9 // Progressive alignment according to a diffs tree.
\r
11 static void MakeNode(const MSA &msaIn, const Tree &Diffs, unsigned uDiffsNodeIndex,
\r
12 const unsigned IdToDiffsTreeNodeIndex[], ProgNode &Node)
\r
14 const unsigned uSeqCount = msaIn.GetSeqCount();
\r
16 unsigned *Ids = new unsigned[uSeqCount];
\r
18 unsigned uSeqsInDiffCount = 0;
\r
19 for (unsigned uId = 0; uId < uSeqCount; ++uId)
\r
21 if (IdToDiffsTreeNodeIndex[uId] == uDiffsNodeIndex)
\r
23 Ids[uSeqsInDiffCount] = uId;
\r
27 if (0 == uSeqsInDiffCount)
\r
28 Quit("MakeNode: no seqs in diff");
\r
30 MSASubsetByIds(msaIn, Ids, uSeqsInDiffCount, Node.m_MSA);
\r
33 ValidateMuscleIds(Node.m_MSA);
\r
36 DeleteGappedCols(Node.m_MSA);
\r
40 void RealignDiffs(const MSA &msaIn, const Tree &Diffs,
\r
41 const unsigned IdToDiffsTreeNodeIndex[], MSA &msaOut)
\r
43 assert(Diffs.IsRooted());
\r
46 Log("RealignDiffs\n");
\r
47 Log("Diff tree:\n");
\r
51 const unsigned uNodeCount = Diffs.GetNodeCount();
\r
52 if (uNodeCount%2 == 0)
\r
53 Quit("RealignDiffs: Expected odd number of nodes");
\r
55 const unsigned uMergeCount = (uNodeCount - 1)/2;
\r
57 ProgNode *ProgNodes = new ProgNode[uNodeCount];
\r
60 SetProgressDesc("Refine tree");
\r
61 for (unsigned uDiffsNodeIndex = Diffs.FirstDepthFirstNode();
\r
62 NULL_NEIGHBOR != uDiffsNodeIndex;
\r
63 uDiffsNodeIndex = Diffs.NextDepthFirstNode(uDiffsNodeIndex))
\r
65 if (Diffs.IsLeaf(uDiffsNodeIndex))
\r
67 assert(uDiffsNodeIndex < uNodeCount);
\r
68 if (uDiffsNodeIndex >= uNodeCount)
\r
69 Quit("TreeNodeIndex=%u NodeCount=%u\n", uDiffsNodeIndex, uNodeCount);
\r
71 ProgNode &Node = ProgNodes[uDiffsNodeIndex];
\r
72 MakeNode(msaIn, Diffs, uDiffsNodeIndex, IdToDiffsTreeNodeIndex, Node);
\r
74 Node.m_uLength = Node.m_MSA.GetColCount();
\r
78 Progress(uJoin, uMergeCount);
\r
80 const unsigned uMergeNodeIndex = uDiffsNodeIndex;
\r
81 ProgNode &Parent = ProgNodes[uMergeNodeIndex];
\r
83 const unsigned uLeft = Diffs.GetLeft(uDiffsNodeIndex);
\r
84 const unsigned uRight = Diffs.GetRight(uDiffsNodeIndex);
\r
86 ProgNode &Node1 = ProgNodes[uLeft];
\r
87 ProgNode &Node2 = ProgNodes[uRight];
\r
90 AlignTwoMSAs(Node1.m_MSA, Node2.m_MSA, Parent.m_MSA, Path);
\r
95 Parent.m_MSA.LogMe();
\r
99 Node1.m_MSA.Clear();
\r
100 Node2.m_MSA.Clear();
\r
103 ProgressStepsDone();
\r
105 unsigned uRootNodeIndex = Diffs.GetRootNodeIndex();
\r
106 const ProgNode &RootProgNode = ProgNodes[uRootNodeIndex];
\r
107 msaOut.Copy(RootProgNode.m_MSA);
\r
110 AssertMSAEqIgnoreCaseAndGaps(msaIn, msaOut);
\r
113 delete[] ProgNodes;
\r