12 static void PathSeq(const Seq &s, const PWPath &Path, bool bRight, Seq &sOut)
\r
16 PathToEstrings(Path, &esA, &esB);
\r
18 const unsigned uSeqLength = s.Length();
\r
19 const unsigned uEdgeCount = Path.GetEdgeCount();
\r
22 sOut.SetName(s.GetName());
\r
24 for (unsigned uEdgeIndex = 0; uEdgeIndex < uEdgeCount; ++uEdgeIndex)
\r
26 const PWEdge &Edge = Path.GetEdge(uEdgeIndex);
\r
27 char cType = Edge.cType;
\r
32 else if (cType == 'D')
\r
38 sOut.AppendChar(s[uPos++]);
\r
41 sOut.AppendChar('-');
\r
44 sOut.AppendChar(s[uPos++]);
\r
47 Quit("PathSeq, invalid edge type %c", cType);
\r
54 static void MakeRootSeq(const Seq &s, const Tree &GuideTree, unsigned uLeafNodeIndex,
\r
55 const ProgNode Nodes[], Seq &sRoot)
\r
58 unsigned uNodeIndex = uLeafNodeIndex;
\r
61 unsigned uParent = GuideTree.GetParent(uNodeIndex);
\r
62 if (NULL_NEIGHBOR == uParent)
\r
64 bool bRight = (GuideTree.GetLeft(uParent) == uNodeIndex);
\r
65 uNodeIndex = uParent;
\r
66 const PWPath &Path = Nodes[uNodeIndex].m_Path;
\r
68 PathSeq(sRoot, Path, bRight, sTmp);
\r
76 static short *MakeRootSeqE(const Seq &s, const Tree &GuideTree, unsigned uLeafNodeIndex,
\r
77 const ProgNode Nodes[], Seq &sRoot, short *Estring1, short *Estring2)
\r
79 short *EstringCurr = Estring1;
\r
80 short *EstringNext = Estring2;
\r
82 const unsigned uSeqLength = s.Length();
\r
83 EstringCurr[0] = uSeqLength;
\r
86 unsigned uNodeIndex = uLeafNodeIndex;
\r
89 unsigned uParent = GuideTree.GetParent(uNodeIndex);
\r
90 if (NULL_NEIGHBOR == uParent)
\r
92 bool bRight = (GuideTree.GetLeft(uParent) == uNodeIndex);
\r
93 uNodeIndex = uParent;
\r
94 const PWPath &Path = Nodes[uNodeIndex].m_Path;
\r
95 const short *EstringNode = bRight ?
\r
96 Nodes[uNodeIndex].m_EstringL : Nodes[uNodeIndex].m_EstringR;
\r
98 MulEstrings(EstringCurr, EstringNode, EstringNext);
\r
102 LogEstring(EstringCurr);
\r
105 LogEstring(EstringNode);
\r
108 LogEstring(EstringNext);
\r
111 short *EstringTmp = EstringNext;
\r
112 EstringNext = EstringCurr;
\r
113 EstringCurr = EstringTmp;
\r
115 EstringOp(EstringCurr, s, sRoot);
\r
118 Log("Root estring=");
\r
119 LogEstring(EstringCurr);
\r
124 return EstringCurr;
\r
127 static unsigned GetFirstNodeIndex(const Tree &tree)
\r
131 return tree.FirstDepthFirstNode();
\r
134 static unsigned GetNextNodeIndex(const Tree &tree, unsigned uPrevNodeIndex)
\r
138 const unsigned uNodeCount = tree.GetNodeCount();
\r
139 unsigned uNodeIndex = uPrevNodeIndex;
\r
143 if (uNodeIndex >= uNodeCount)
\r
144 return NULL_NEIGHBOR;
\r
145 if (tree.IsLeaf(uNodeIndex))
\r
149 unsigned uNodeIndex = uPrevNodeIndex;
\r
152 uNodeIndex = tree.NextDepthFirstNode(uNodeIndex);
\r
153 if (NULL_NEIGHBOR == uNodeIndex || tree.IsLeaf(uNodeIndex))
\r
158 void MakeRootMSA(const SeqVect &v, const Tree &GuideTree, ProgNode Nodes[],
\r
162 Log("MakeRootMSA Tree=");
\r
165 const unsigned uSeqCount = v.GetSeqCount();
\r
166 unsigned uColCount = uInsane;
\r
167 unsigned uSeqIndex = 0;
\r
168 const unsigned uTreeNodeCount = GuideTree.GetNodeCount();
\r
169 const unsigned uRootNodeIndex = GuideTree.GetRootNodeIndex();
\r
170 const PWPath &RootPath = Nodes[uRootNodeIndex].m_Path;
\r
171 const unsigned uRootColCount = RootPath.GetEdgeCount();
\r
172 const unsigned uEstringSize = uRootColCount + 1;
\r
173 short *Estring1 = new short[uEstringSize];
\r
174 short *Estring2 = new short[uEstringSize];
\r
175 SetProgressDesc("Root alignment");
\r
177 unsigned uTreeNodeIndex = GetFirstNodeIndex(GuideTree);
\r
180 Progress(uSeqIndex, uSeqCount);
\r
182 unsigned uId = GuideTree.GetLeafId(uTreeNodeIndex);
\r
183 const Seq &s = *(v[uId]);
\r
186 short *es = MakeRootSeqE(s, GuideTree, uTreeNodeIndex, Nodes, sRootE,
\r
187 Estring1, Estring2);
\r
188 Nodes[uTreeNodeIndex].m_EstringL = EstringNewCopy(es);
\r
192 MakeRootSeq(s, GuideTree, uTreeNodeIndex, Nodes, sRoot);
\r
193 if (!sRoot.Eq(sRootE))
\r
199 Quit("Root seqs differ");
\r
202 Log("MakeRootSeq=\n");
\r
207 if (uInsane == uColCount)
\r
209 uColCount = sRootE.Length();
\r
210 a.SetSize(uSeqCount, uColCount);
\r
214 assert(uColCount == sRootE.Length());
\r
216 a.SetSeqName(uSeqIndex, s.GetName());
\r
217 a.SetSeqId(uSeqIndex, uId);
\r
218 for (unsigned uColIndex = 0; uColIndex < uColCount; ++uColIndex)
\r
219 a.SetChar(uSeqIndex, uColIndex, sRootE[uColIndex]);
\r
222 uTreeNodeIndex = GetNextNodeIndex(GuideTree, uTreeNodeIndex);
\r
224 while (NULL_NEIGHBOR != uTreeNodeIndex);
\r
229 ProgressStepsDone();
\r
230 assert(uSeqIndex == uSeqCount);
\r