binaries/src/muscle/progressivealign.cpp

   1 #include "muscle.h"\r
   2 #include <math.h>\r
   3 #include "tree.h"\r
   4 #include "seqvect.h"\r
   5 #include "profile.h"\r
   6 #include "msa.h"\r
   7 #include "pwpath.h"\r
   8 #include "distfunc.h"\r
   9 \r
  10 #define TRACE 0\r
  11 \r
  12 void ProgressiveAlign(const SeqVect &v, const Tree &GuideTree, MSA &a)\r
  13         {\r
  14         assert(GuideTree.IsRooted());\r
  15 \r
  16 #if     TRACE\r
  17         Log("GuideTree:\n");\r
  18         GuideTree.LogMe();\r
  19 #endif\r
  20 \r
  21         const unsigned uSeqCount = v.Length();\r
  22         const unsigned uNodeCount = 2*uSeqCount - 1;\r
  23 \r
  24         ProgNode *ProgNodes = new ProgNode[uNodeCount];\r
  25 \r
  26         unsigned uJoin = 0;\r
  27         unsigned uTreeNodeIndex = GuideTree.FirstDepthFirstNode();\r
  28         SetProgressDesc("Align node");\r
  29         do\r
  30                 {\r
  31                 if (GuideTree.IsLeaf(uTreeNodeIndex))\r
  32                         {\r
  33                         if (uTreeNodeIndex >= uNodeCount)\r
  34                                 Quit("TreeNodeIndex=%u NodeCount=%u\n", uTreeNodeIndex, uNodeCount);\r
  35                         ProgNode &Node = ProgNodes[uTreeNodeIndex];\r
  36                         unsigned uId = GuideTree.GetLeafId(uTreeNodeIndex);\r
  37                         if (uId >= uSeqCount)\r
  38                                 Quit("Seq index out of range");\r
  39                         const Seq &s = *(v[uId]);\r
  40                         Node.m_MSA.FromSeq(s);\r
  41                         Node.m_MSA.SetSeqId(0, uId);\r
  42                         Node.m_uLength = Node.m_MSA.GetColCount();\r
  43                         }\r
  44                 else\r
  45                         {\r
  46                         Progress(uJoin, uSeqCount - 1);\r
  47                         ++uJoin;\r
  48 \r
  49                         const unsigned uMergeNodeIndex = uTreeNodeIndex;\r
  50                         ProgNode &Parent = ProgNodes[uMergeNodeIndex];\r
  51 \r
  52                         const unsigned uLeft = GuideTree.GetLeft(uTreeNodeIndex);\r
  53                         const unsigned uRight = GuideTree.GetRight(uTreeNodeIndex);\r
  54 \r
  55                         ProgNode &Node1 = ProgNodes[uLeft];\r
  56                         ProgNode &Node2 = ProgNodes[uRight];\r
  57 \r
  58                         PWPath Path;\r
  59                         AlignTwoMSAs(Node1.m_MSA, Node2.m_MSA, Parent.m_MSA, Path);\r
  60                         Parent.m_uLength = Parent.m_MSA.GetColCount();\r
  61 \r
  62                         Node1.m_MSA.Clear();\r
  63                         Node2.m_MSA.Clear();\r
  64                         }\r
  65                 uTreeNodeIndex = GuideTree.NextDepthFirstNode(uTreeNodeIndex);\r
  66                 }\r
  67         while (NULL_NEIGHBOR != uTreeNodeIndex);\r
  68         ProgressStepsDone();\r
  69 \r
  70         unsigned uRootNodeIndex = GuideTree.GetRootNodeIndex();\r
  71         const ProgNode &RootProgNode = ProgNodes[uRootNodeIndex];\r
  72         a.Copy(RootProgNode.m_MSA);\r
  73 \r
  74         delete[] ProgNodes;\r
  75         ProgNodes = 0;\r
  76         }\r