Why neighbor-joining works
| dc.creator | Mihaescu, Radu | |
| dc.creator | Levy, Dan | |
| dc.creator | Pachter, Lior | |
| dc.date | 2006-02-10 | |
| dc.date | 2007-06-17 | |
| dc.date.accessioned | 2026-07-07T08:10:18Z | |
| dc.date.available | 2026-07-07T08:10:18Z | |
| dc.description | We show that the neighbor-joining algorithm is a robust quartet method for constructing trees from distances. This leads to a new performance guarantee that contains Atteson's optimal radius bound as a special case and explains many cases where neighbor-joining is successful even when Atteson's criterion is not satisfied. We also provide a proof for Atteson's conjecture on the optimal edge radius of the neighbor-joining algorithm. The strong performance guarantees we provide also hold for the quadratic time fast neighbor-joining algorithm, thus providing a theoretical basis for inferring very large phylogenies with neighbor-joining. | |
| dc.description | Revision 2 | |
| dc.identifier | https://arxiv.org/abs/cs/0602041 | |
| dc.identifier | http://arxiv.org/abs/cs/0602041 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/131786 | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | Discrete Mathematics | |
| dc.subject | F.2.0 | |
| dc.title | Why neighbor-joining works | |
| dc.type | text |