開發用於樹突變

我必須拿出一個高效的算法，需要在此格式的樹的運算法則：開發用於樹突變

?   
/\  
    ? ?  
/\/\ 
G A A A

，並與提供突變量最少值的問號節點填充。這些值只能是{A，C，T，G}。樹將始終具有相同的形狀和節點數量。此外，它將始終填充葉節點，其餘節點將成爲需要填充的問號。

例如，右邊的樹是正確的，比左邊的樹少突變。

A   A 
/\  /\ 
    G G  A A 
/\/\ /\/\ 
G A A A G A A A

當父節點與子節點不同時，會發生突變。所以，上面的左樹包含五個突變，右上方有一個突變。

有人可以通過提供psuedocode幫助我嗎？謝謝。

來源

2012-11-05 MCR

你如何定義一個突變？我對生物學沒有深入的瞭解。（請編輯您的問題以包含此信息） – nhahtdh

您需要提供更多信息。根據你的邏輯，一棵具有所有A的樹將具有最少的突變，但是具有所有A的樹不包含任何具有生物重要性的數據。 –

是否所有的輸入樹都具有用字母填充的葉單元和所有其他節點中的問號？樹總是二叉樹嗎？ –

這看起來像從樹底向上的動態編程。對於每個節點，您想要制定最節省的解決方案，使每個節點都標記爲A，C，T或G.您通過使用之前計算的成本來計算緊接在該節點下的節點的每種可能性的成本。只是計算成本的代碼可能有點像這樣。

LeastCost(node, colourHere) 
{ 
    foreach colour 
    leastLeft[colour] = LeastCost(leftChild, colour) 
    leastRight[colour] = LeastCost(rightChild, colour) 
    best = infinity 
    foreach combination 
    cost = leastLeft[combination.leftColour] + 
     leastRight[combination.rightColour] 
    if (combination.leftColour != colourHere) 
     cost++; 
    if (combination.rightColour != colourHere) 
     cost++; 
    if (cost < best) 
     cost = best; 
    return cost 
}

要返回最佳答案以及最佳成本，您需要跟蹤對應於最佳答案的組合。仔細想想，您可以通過在每個節點同時計算所有四種顏色的答案來節省時間。

來源

2012-11-05 04:49:23 mcdowella

開發用於樹突變

回答

相關問題