Combinatorial and computational investigations of Neighbor-Joining bias
The Neighbor-Joining algorithm is a popular distance-based phylogenetic method that computes a tree metric from a dissimilarity map arising from biological data. Realizing dissimilarity maps as points in Euclidean space, the algorithm partitions the input space into polyhedral regions indexed by the combinatorial type of the trees returned. A full combinatorial description of these regions has not been found yet; different sequences of Neighbor-Joining agglomeration events can produce the same combinatorial tree, therefore associating multiple geometric regions to the same algorithmic output. We resolve this confusion by defining agglomeration orders on trees, leading to a bijection between distinct regions of the output space and weighted Motzkin paths. As a result, we give a formula for the number of polyhedral regions depending only on the number of taxa. We conclude with a computational comparison between these polyhedral regions, to unveil biases introduced in any implementation of the algorithm.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Neighbor Joining And Leaf Status
The Neighbor Joining Algorithm is among the most fundamental algorithmic results in computational biology. However, its definition and correctness proof are not straightforward. In particular, ''the question ''what does …
A Lie-algebraic perspective on Tree-Adjoining Grammars
We provide a novel mathematical implementation of tree-adjoining grammars using two combinatorial definitions of graphs. With this lens, we demonstrate that the adjoining operation defines a pre-Lie operation and subsequ…
A 4-approximation algorithm for min max correlation clustering
We introduce a lower bounding technique for the min max correlation clustering problem and, based on this technique, a combinatorial 4-approximation algorithm for complete graphs. This improves upon the previous best kno…
ClusteringSketching Method for Large Scale Combinatorial Inference
We present computationally efficient algorithms to test various combinatorial structures of large-scale graphical models. In order to test the hypotheses on their topological structures, we propose two adjacency matrix s…
regressionLearning with Local Search MCMC Layers
Integrating combinatorial optimization layers into neural networks has recently attracted significant research interest. However, many existing approaches lack theoretical guarantees or fail to perform adequately when re…
Combinatorial Optimization