Numerical taxonomy on data: Experimental results

Jaime Cohen; Martin Farach

Numerical taxonomy on data: Experimental results

Jaime Cohen, Martin Farach

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

Abstract

We consider the problem of fitting an n×n distance matrix D by a tree metric T. This problem is NP-hard for most reasonable distance functions between D and T. Recently, an approximation algorithm was presented which achieves a factor of 3 approximation to the L_∞ best fitting tree. We call this method the Single Pivot (SP) heuristic. Within the biology community, the so-called Neighbor-Joining (NY) heuristic has wide acceptance. In this paper, we introduced a new Double Pivot (DP) heuristic, which is an extension of the SP heuristic, and show that DP outperforms NJ on biological and random data.

Original language	English (US)
Pages	410-417
Number of pages	8
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

Other

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

ASJC Scopus subject areas

Software
General Mathematics

Cite this

@conference{a8eba8b9d0f741a4ab1cbe954e32be12,

title = "Numerical taxonomy on data: Experimental results",

abstract = "We consider the problem of fitting an n×n distance matrix D by a tree metric T. This problem is NP-hard for most reasonable distance functions between D and T. Recently, an approximation algorithm was presented which achieves a factor of 3 approximation to the L∞ best fitting tree. We call this method the Single Pivot (SP) heuristic. Within the biology community, the so-called Neighbor-Joining (NY) heuristic has wide acceptance. In this paper, we introduced a new Double Pivot (DP) heuristic, which is an extension of the SP heuristic, and show that DP outperforms NJ on biological and random data.",

author = "Jaime Cohen and Martin Farach",

year = "1997",

language = "English (US)",

pages = "410--417",

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 - Numerical taxonomy on data

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

AU - Cohen, Jaime

AU - Farach, Martin

PY - 1997

Y1 - 1997

N2 - We consider the problem of fitting an n×n distance matrix D by a tree metric T. This problem is NP-hard for most reasonable distance functions between D and T. Recently, an approximation algorithm was presented which achieves a factor of 3 approximation to the L∞ best fitting tree. We call this method the Single Pivot (SP) heuristic. Within the biology community, the so-called Neighbor-Joining (NY) heuristic has wide acceptance. In this paper, we introduced a new Double Pivot (DP) heuristic, which is an extension of the SP heuristic, and show that DP outperforms NJ on biological and random data.

AB - We consider the problem of fitting an n×n distance matrix D by a tree metric T. This problem is NP-hard for most reasonable distance functions between D and T. Recently, an approximation algorithm was presented which achieves a factor of 3 approximation to the L∞ best fitting tree. We call this method the Single Pivot (SP) heuristic. Within the biology community, the so-called Neighbor-Joining (NY) heuristic has wide acceptance. In this paper, we introduced a new Double Pivot (DP) heuristic, which is an extension of the SP heuristic, and show that DP outperforms NJ on biological and random data.

UR - http://www.scopus.com/inward/record.url?scp=0030733702&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0030733702&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:0030733702

SP - 410

EP - 417

Y2 - 5 January 1997 through 7 January 1997

ER -

Numerical taxonomy on data: Experimental results

Abstract

Other

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this