+++ /dev/null
-#include "muscle.h"\r
-#include "msa.h"\r
-#include "tree.h"\r
-#include "profile.h"\r
-#include "pwpath.h"\r
-\r
-#define TRACE 0\r
-\r
-// Progressive alignment according to a diffs tree.\r
-\r
-static void MakeNode(const MSA &msaIn, const Tree &Diffs, unsigned uDiffsNodeIndex,\r
- const unsigned IdToDiffsTreeNodeIndex[], ProgNode &Node)\r
- {\r
- const unsigned uSeqCount = msaIn.GetSeqCount();\r
-\r
- unsigned *Ids = new unsigned[uSeqCount];\r
-\r
- unsigned uSeqsInDiffCount = 0;\r
- for (unsigned uId = 0; uId < uSeqCount; ++uId)\r
- {\r
- if (IdToDiffsTreeNodeIndex[uId] == uDiffsNodeIndex)\r
- {\r
- Ids[uSeqsInDiffCount] = uId;\r
- ++uSeqsInDiffCount;\r
- }\r
- }\r
- if (0 == uSeqsInDiffCount)\r
- Quit("MakeNode: no seqs in diff");\r
-\r
- MSASubsetByIds(msaIn, Ids, uSeqsInDiffCount, Node.m_MSA);\r
-\r
-#if DEBUG\r
- ValidateMuscleIds(Node.m_MSA);\r
-#endif\r
-\r
- DeleteGappedCols(Node.m_MSA);\r
- delete[] Ids;\r
- }\r
-\r
-void RealignDiffs(const MSA &msaIn, const Tree &Diffs,\r
- const unsigned IdToDiffsTreeNodeIndex[], MSA &msaOut)\r
- {\r
- assert(Diffs.IsRooted());\r
-\r
-#if TRACE\r
- Log("RealignDiffs\n");\r
- Log("Diff tree:\n");\r
- Diffs.LogMe();\r
-#endif\r
-\r
- const unsigned uNodeCount = Diffs.GetNodeCount();\r
- if (uNodeCount%2 == 0)\r
- Quit("RealignDiffs: Expected odd number of nodes");\r
-\r
- const unsigned uMergeCount = (uNodeCount - 1)/2;\r
-\r
- ProgNode *ProgNodes = new ProgNode[uNodeCount];\r
-\r
- unsigned uJoin = 0;\r
- SetProgressDesc("Refine tree");\r
- for (unsigned uDiffsNodeIndex = Diffs.FirstDepthFirstNode();\r
- NULL_NEIGHBOR != uDiffsNodeIndex;\r
- uDiffsNodeIndex = Diffs.NextDepthFirstNode(uDiffsNodeIndex))\r
- {\r
- if (Diffs.IsLeaf(uDiffsNodeIndex))\r
- {\r
- assert(uDiffsNodeIndex < uNodeCount);\r
- if (uDiffsNodeIndex >= uNodeCount)\r
- Quit("TreeNodeIndex=%u NodeCount=%u\n", uDiffsNodeIndex, uNodeCount);\r
-\r
- ProgNode &Node = ProgNodes[uDiffsNodeIndex];\r
- MakeNode(msaIn, Diffs, uDiffsNodeIndex, IdToDiffsTreeNodeIndex, Node);\r
-\r
- Node.m_uLength = Node.m_MSA.GetColCount();\r
- }\r
- else\r
- {\r
- Progress(uJoin, uMergeCount);\r
- ++uJoin;\r
- const unsigned uMergeNodeIndex = uDiffsNodeIndex;\r
- ProgNode &Parent = ProgNodes[uMergeNodeIndex];\r
-\r
- const unsigned uLeft = Diffs.GetLeft(uDiffsNodeIndex);\r
- const unsigned uRight = Diffs.GetRight(uDiffsNodeIndex);\r
-\r
- ProgNode &Node1 = ProgNodes[uLeft];\r
- ProgNode &Node2 = ProgNodes[uRight];\r
-\r
- PWPath Path;\r
- AlignTwoMSAs(Node1.m_MSA, Node2.m_MSA, Parent.m_MSA, Path);\r
-\r
-#if TRACE\r
- {\r
- Log("Combined:\n");\r
- Parent.m_MSA.LogMe();\r
- }\r
-#endif\r
-\r
- Node1.m_MSA.Clear();\r
- Node2.m_MSA.Clear();\r
- }\r
- }\r
- ProgressStepsDone();\r
-\r
- unsigned uRootNodeIndex = Diffs.GetRootNodeIndex();\r
- const ProgNode &RootProgNode = ProgNodes[uRootNodeIndex];\r
- msaOut.Copy(RootProgNode.m_MSA);\r
-\r
-#if DEBUG\r
- AssertMSAEqIgnoreCaseAndGaps(msaIn, msaOut);\r
-#endif\r
-\r
- delete[] ProgNodes;\r
- ProgNodes = 0;\r
- }\r