amnh / PCG

𝙋𝙝𝙮𝙡𝙤𝙜𝙚𝙣𝙚𝙩𝙞𝙘 𝘾𝙤𝙢𝙥𝙤𝙣𝙚𝙣𝙩 𝙂𝙧𝙖𝙥𝙝 ⸺ Haskell program and libraries for general phylogenetic graph search
28 stars 1 forks source link

Incorrect network cost quantification #50

Closed recursion-ninja closed 7 years ago

recursion-ninja commented 7 years ago

The network cost is not being correctly calculated.

Suppose you had 5 character blocks across 3 resolutions with the following costs:

X A B C D E
R1 5 6 7 2 6
R2 6 8 9 2 3
R3 4 9 7 2 5

Incorrect Algorithm:

We are currently (incorrectly) summing the characters of a resolution:

X Sum
R1 26
R2 28
R3 27

Then taking the minimum cost resolution:

X Sum
Min ([R3],24)

Correct Algorithm:

We need to select the minimum resolution for each character:

X A B C D E
Min ([R3],4) ([R1],6) ([R1,R3],7) ([R1,R2,R3],2) ([R2],3)

Then taking the minimum cost resolution:

X Sum
Min ([R1,R2,R3],22)
recursion-ninja commented 7 years ago

This minimization error has been corrected and merged back into master with commit 1527959.