On distances between phylogenetic trees

B. DasGupta; X. He; T. Jiang; M. Li; J. Tromp; L. Zhang

On distances between phylogenetic trees

B. DasGupta
, X. He
, T. Jiang
, M. Li
, J. Tromp
, L. Zhang

Department of Computer Science and Engineering

Rutgers - The State University of New Jersey, Camden

Research output: Contribution to conference › Paper › peer-review

83 Scopus citations

Abstract

Approximation algorithms for computing the nearest neighbor interchange (nni) distance and the subtree-transfer distance in phylogenetic trees describing molecular evolution are presented. The computation of nni distance is taken to be an NP-complete problem. An algorithm for computing the nni sequence in time O(n²log n+n.2^O(d)), where d is the maximum nni distance, is presented. Biological applications require the extension of the nni and cost transfer models to weighted phylogenies, where edge weights indicate the length of evolution along each edge. Thus, a logarithmic ratio approximation algorithm for nni and a ratio 2 approximation algorithm for linear-cost, subtree-transfer on weighted trees are presented.

Original language	English
Pages	427-436
Number of pages	10
State	Published - 1997
Event	Proceedings of the 1996 8th Annual ACM-SIAM Symposium on Discrete Algorithms - New Orleans, LA, USA Duration: Jan 5 1997 → Jan 7 1997

Conference

Conference	Proceedings of the 1996 8th Annual ACM-SIAM Symposium on Discrete Algorithms
City	New Orleans, LA, USA
Period	01/5/97 → 01/7/97

Cite this

@conference{092e44212c6f4552b520b8eee6a6bb63,

title = "On distances between phylogenetic trees",

abstract = "Approximation algorithms for computing the nearest neighbor interchange (nni) distance and the subtree-transfer distance in phylogenetic trees describing molecular evolution are presented. The computation of nni distance is taken to be an NP-complete problem. An algorithm for computing the nni sequence in time O(n2log n+n.2O(d)), where d is the maximum nni distance, is presented. Biological applications require the extension of the nni and cost transfer models to weighted phylogenies, where edge weights indicate the length of evolution along each edge. Thus, a logarithmic ratio approximation algorithm for nni and a ratio 2 approximation algorithm for linear-cost, subtree-transfer on weighted trees are presented.",

author = "B. DasGupta and X. He and T. Jiang and M. Li and J. Tromp and L. Zhang",

year = "1997",

language = "English",

pages = "427--436",

note = "Proceedings of the 1996 8th Annual ACM-SIAM Symposium on Discrete Algorithms ; Conference date: 05-01-1997 Through 07-01-1997",

}

TY - CONF

T1 - On distances between phylogenetic trees

AU - DasGupta, B.

AU - He, X.

AU - Jiang, T.

AU - Li, M.

AU - Tromp, J.

AU - Zhang, L.

PY - 1997

Y1 - 1997

N2 - Approximation algorithms for computing the nearest neighbor interchange (nni) distance and the subtree-transfer distance in phylogenetic trees describing molecular evolution are presented. The computation of nni distance is taken to be an NP-complete problem. An algorithm for computing the nni sequence in time O(n2log n+n.2O(d)), where d is the maximum nni distance, is presented. Biological applications require the extension of the nni and cost transfer models to weighted phylogenies, where edge weights indicate the length of evolution along each edge. Thus, a logarithmic ratio approximation algorithm for nni and a ratio 2 approximation algorithm for linear-cost, subtree-transfer on weighted trees are presented.

AB - Approximation algorithms for computing the nearest neighbor interchange (nni) distance and the subtree-transfer distance in phylogenetic trees describing molecular evolution are presented. The computation of nni distance is taken to be an NP-complete problem. An algorithm for computing the nni sequence in time O(n2log n+n.2O(d)), where d is the maximum nni distance, is presented. Biological applications require the extension of the nni and cost transfer models to weighted phylogenies, where edge weights indicate the length of evolution along each edge. Thus, a logarithmic ratio approximation algorithm for nni and a ratio 2 approximation algorithm for linear-cost, subtree-transfer on weighted trees are presented.

UR - https://www.scopus.com/pages/publications/0030783392

M3 - Paper

AN - SCOPUS:0030783392

SP - 427

EP - 436

T2 - Proceedings of the 1996 8th Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 5 January 1997 through 7 January 1997

ER -

On distances between phylogenetic trees

Abstract

Conference

Other files and links

Fingerprint

Cite this