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
75 static short *MakeRootSeqE(const Seq &s, const Tree &GuideTree, unsigned uLeafNodeIndex,
\r
76 const ProgNode Nodes[], Seq &sRoot, short *Estring1, short *Estring2)
\r
78 short *EstringCurr = Estring1;
\r
79 short *EstringNext = Estring2;
\r
81 const unsigned uSeqLength = s.Length();
\r
82 EstringCurr[0] = uSeqLength;
\r
85 unsigned uNodeIndex = uLeafNodeIndex;
\r
88 unsigned uParent = GuideTree.GetParent(uNodeIndex);
\r
89 if (NULL_NEIGHBOR == uParent)
\r
91 bool bRight = (GuideTree.GetLeft(uParent) == uNodeIndex);
\r
92 uNodeIndex = uParent;
\r
93 const PWPath &Path = Nodes[uNodeIndex].m_Path;
\r
94 const short *EstringNode = bRight ?
\r
95 Nodes[uNodeIndex].m_EstringL : Nodes[uNodeIndex].m_EstringR;
\r
97 MulEstrings(EstringCurr, EstringNode, EstringNext);
\r
101 LogEstring(EstringCurr);
\r
104 LogEstring(EstringNode);
\r
107 LogEstring(EstringNext);
\r
110 short *EstringTmp = EstringNext;
\r
111 EstringNext = EstringCurr;
\r
112 EstringCurr = EstringTmp;
\r
114 EstringOp(EstringCurr, s, sRoot);
\r
117 Log("Root estring=");
\r
118 LogEstring(EstringCurr);
\r
123 return EstringCurr;
\r
126 static unsigned GetFirstNodeIndex(const Tree &tree)
\r
130 return tree.FirstDepthFirstNode();
\r
133 static unsigned GetNextNodeIndex(const Tree &tree, unsigned uPrevNodeIndex)
\r
137 const unsigned uNodeCount = tree.GetNodeCount();
\r
138 unsigned uNodeIndex = uPrevNodeIndex;
\r
142 if (uNodeIndex >= uNodeCount)
\r
143 return NULL_NEIGHBOR;
\r
144 if (tree.IsLeaf(uNodeIndex))
\r
148 unsigned uNodeIndex = uPrevNodeIndex;
\r
151 uNodeIndex = tree.NextDepthFirstNode(uNodeIndex);
\r
152 if (NULL_NEIGHBOR == uNodeIndex || tree.IsLeaf(uNodeIndex))
\r
157 void MakeRootMSA(const SeqVect &v, const Tree &GuideTree, ProgNode Nodes[],
\r
161 Log("MakeRootMSA Tree=");
\r
164 const unsigned uSeqCount = v.GetSeqCount();
\r
165 unsigned uColCount = uInsane;
\r
166 unsigned uSeqIndex = 0;
\r
167 const unsigned uTreeNodeCount = GuideTree.GetNodeCount();
\r
168 const unsigned uRootNodeIndex = GuideTree.GetRootNodeIndex();
\r
169 const PWPath &RootPath = Nodes[uRootNodeIndex].m_Path;
\r
170 const unsigned uRootColCount = RootPath.GetEdgeCount();
\r
171 const unsigned uEstringSize = uRootColCount + 1;
\r
172 short *Estring1 = new short[uEstringSize];
\r
173 short *Estring2 = new short[uEstringSize];
\r
174 SetProgressDesc("Root alignment");
\r
176 unsigned uTreeNodeIndex = GetFirstNodeIndex(GuideTree);
\r
179 Progress(uSeqIndex, uSeqCount);
\r
181 unsigned uId = GuideTree.GetLeafId(uTreeNodeIndex);
\r
182 const Seq &s = *(v[uId]);
\r
185 short *es = MakeRootSeqE(s, GuideTree, uTreeNodeIndex, Nodes, sRootE,
\r
186 Estring1, Estring2);
\r
187 Nodes[uTreeNodeIndex].m_EstringL = EstringNewCopy(es);
\r
191 MakeRootSeq(s, GuideTree, uTreeNodeIndex, Nodes, sRoot);
\r
192 if (!sRoot.Eq(sRootE))
\r
198 Quit("Root seqs differ");
\r
203 Log("MakeRootSeq=\n");
\r
206 if (uInsane == uColCount)
\r
208 uColCount = sRootE.Length();
\r
209 a.SetSize(uSeqCount, uColCount);
\r
213 assert(uColCount == sRootE.Length());
\r
215 a.SetSeqName(uSeqIndex, s.GetName());
\r
216 a.SetSeqId(uSeqIndex, uId);
\r
217 for (unsigned uColIndex = 0; uColIndex < uColCount; ++uColIndex)
\r
218 a.SetChar(uSeqIndex, uColIndex, sRootE[uColIndex]);
\r
221 uTreeNodeIndex = GetNextNodeIndex(GuideTree, uTreeNodeIndex);
\r
223 while (NULL_NEIGHBOR != uTreeNodeIndex);
\r
228 ProgressStepsDone();
\r
229 assert(uSeqIndex == uSeqCount);
\r