An exact algorithm for the minimum quartet tree cost problem

Sergio Consoli*, Jan Korst, Gijs Geleijnse, Steffen Pauws

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

Abstract

The minimum quartet tree cost (MQTC) problem is a graph combinatorial optimization problem where, given a set of n >= 4 quartet topologies on n, where optimality means that the sum of the costs of the embedded (or consistent) quartet topologies is minimal. The MQTC problem is the foundation of the quartet method of hierarchical clustering, a novel hierarchical clustering method for non tree-like (non-phylogeny) data in various domains, or for heterogeneous data across domains. The MQTC problem is NP-complete and some heuristics have been already proposed in the literature. The aim of this paper is to present a first exact solution approach for the MQTC problem. Although the algorithm is able to get exact solutions only for relatively small problem instances, due to the high problem complexity, it can be used as a benchmark for validating the performance of any heuristic proposed for the MQTC problem.

Original languageEnglish
Pages (from-to)401-425
Number of pages25
Journal4or-A quarterly journal of operations research
Volume17
Issue number4
DOIs
Publication statusPublished - Jun 2019

Keywords

  • Combinatorial optimization
  • Quartet trees
  • Minimum quartet tree cost
  • Exact solution algorithms
  • Cluster analysis
  • Graphs

Cite this

Consoli, Sergio ; Korst, Jan ; Geleijnse, Gijs ; Pauws, Steffen. / An exact algorithm for the minimum quartet tree cost problem. In: 4or-A quarterly journal of operations research. 2019 ; Vol. 17, No. 4. pp. 401-425.
@article{bf03c47796814650a3ac7a42bce4170d,
title = "An exact algorithm for the minimum quartet tree cost problem",
abstract = "The minimum quartet tree cost (MQTC) problem is a graph combinatorial optimization problem where, given a set of n >= 4 quartet topologies on n, where optimality means that the sum of the costs of the embedded (or consistent) quartet topologies is minimal. The MQTC problem is the foundation of the quartet method of hierarchical clustering, a novel hierarchical clustering method for non tree-like (non-phylogeny) data in various domains, or for heterogeneous data across domains. The MQTC problem is NP-complete and some heuristics have been already proposed in the literature. The aim of this paper is to present a first exact solution approach for the MQTC problem. Although the algorithm is able to get exact solutions only for relatively small problem instances, due to the high problem complexity, it can be used as a benchmark for validating the performance of any heuristic proposed for the MQTC problem.",
keywords = "Combinatorial optimization, Quartet trees, Minimum quartet tree cost, Exact solution algorithms, Cluster analysis, Graphs",
author = "Sergio Consoli and Jan Korst and Gijs Geleijnse and Steffen Pauws",
year = "2019",
month = "6",
doi = "10.1007/s10288-018-0394-2",
language = "English",
volume = "17",
pages = "401--425",
journal = "4or-A quarterly journal of operations research",
issn = "1619-4500",
publisher = "SPRINGER HEIDELBERG",
number = "4",

}

An exact algorithm for the minimum quartet tree cost problem. / Consoli, Sergio; Korst, Jan; Geleijnse, Gijs; Pauws, Steffen.

In: 4or-A quarterly journal of operations research, Vol. 17, No. 4, 06.2019, p. 401-425.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - An exact algorithm for the minimum quartet tree cost problem

AU - Consoli, Sergio

AU - Korst, Jan

AU - Geleijnse, Gijs

AU - Pauws, Steffen

PY - 2019/6

Y1 - 2019/6

N2 - The minimum quartet tree cost (MQTC) problem is a graph combinatorial optimization problem where, given a set of n >= 4 quartet topologies on n, where optimality means that the sum of the costs of the embedded (or consistent) quartet topologies is minimal. The MQTC problem is the foundation of the quartet method of hierarchical clustering, a novel hierarchical clustering method for non tree-like (non-phylogeny) data in various domains, or for heterogeneous data across domains. The MQTC problem is NP-complete and some heuristics have been already proposed in the literature. The aim of this paper is to present a first exact solution approach for the MQTC problem. Although the algorithm is able to get exact solutions only for relatively small problem instances, due to the high problem complexity, it can be used as a benchmark for validating the performance of any heuristic proposed for the MQTC problem.

AB - The minimum quartet tree cost (MQTC) problem is a graph combinatorial optimization problem where, given a set of n >= 4 quartet topologies on n, where optimality means that the sum of the costs of the embedded (or consistent) quartet topologies is minimal. The MQTC problem is the foundation of the quartet method of hierarchical clustering, a novel hierarchical clustering method for non tree-like (non-phylogeny) data in various domains, or for heterogeneous data across domains. The MQTC problem is NP-complete and some heuristics have been already proposed in the literature. The aim of this paper is to present a first exact solution approach for the MQTC problem. Although the algorithm is able to get exact solutions only for relatively small problem instances, due to the high problem complexity, it can be used as a benchmark for validating the performance of any heuristic proposed for the MQTC problem.

KW - Combinatorial optimization

KW - Quartet trees

KW - Minimum quartet tree cost

KW - Exact solution algorithms

KW - Cluster analysis

KW - Graphs

U2 - 10.1007/s10288-018-0394-2

DO - 10.1007/s10288-018-0394-2

M3 - Article

VL - 17

SP - 401

EP - 425

JO - 4or-A quarterly journal of operations research

JF - 4or-A quarterly journal of operations research

SN - 1619-4500

IS - 4

ER -