Correction: Journal of Computational Biology: 2014;21/4:303–319

In our article “Exactly Computing the Parsimony Scores on Phylogenetic Networks Using Dynamic Programming” (published in Journal of Computational Biology: 2014; 21/4:303–319) by Lavanya Kannan and Ward C. Wheeler, the authors wish to point out that Lemma 1 is incorrect. The reason for this error is because we used a necessary condition for proving planarity. As a result, the phylogenetic networks that we consider are not necessarily planar. Other results in the manuscript remain unaffected in the absence of this lemma.

A sufficient condition for planarity of a graph is given by Kuratowski's theorem (Kuratowski, 1930) as follows. A subdivision of a graph results from inserting vertices into edges.

Theorem 1 (Kuratowski's theorem): A finite graph is planar if it does not contain a subgraph that is a subdivision of K₅ (the complete graph on five vertices) or K_3,3 (complete bipartite graph on six vertices, three of which connect to each of the other three).

Indeed it would be possible to obtain a phylogenetic network by adding edges and vertices to K_3,3 and directing the edges. A good exercise would then be to obtain phylogenetic network(s) with the minimum number of vertices. We noted earlier in the conclusion of the paper that it has been proven in Hartvigsen (1998) that the hardwired problem is polynomially solvable. In view of this, it would be a worthwhile effort to characterize planar phylogenetic networks. It would be possible to obtain an algorithm for computing the hardwired score on planar phylogenetic networks, perhaps similar to Fitch algorithm (Fitch, 1971) for phylogenetic trees.

Acknowledgment: We thank Mike Steel for rightly pointing out the error that was committed in proving Lemma 1. This went unnoticed until publication. We also assure the readers that the results in the paper are unaffected because of the error, for planarity is not used in any of the results.