Algorithms and software for calculating and visualizing the cardinality of the grand bounding ball by means of intersection trees

Robert Barton, Sen Zhang, Katherine Herbert

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

While it is straightforward to calculate the bounding ball of a partially resolved phylogenetic tree, the calculation of the cardinality of the grand bounding ball for multiple partially resolved trees is very time-consuming due to the power set principle that governs the highly iterative calculation process. What can further complicate the calculation is that the practitioner has to possess domain knowledge in phylogenetic trees, subtree mining and discrete math at the same time. This paper presents the first efficient software to automate the process of calculating the cardinality of the grand bounding ball by combining a number of advanced data mining techniques and concepts including systematically growing intersection trees, which is specially defined for this work, level by level, cluster sets, Apriori, equivalence class, and set theory, and rooting unrooted trees etc. The algorithms are discussed in the the rooted tree scope first; then they are extended to the unrooted tree scope by using a novel directing method. In addition, a displayer component has been implemented to help visualize the complicated calculation process demanded by the problem. The software is expected to be useful in phylogenetic tree clustering research.

Original languageEnglish
Title of host publicationProceedings of the 2008 International Conference on Data Mining, DMIN 2008
EditorsR. Stahlbock, S.F. Crone, S. Lessmann
Pages529-535
Number of pages7
StatePublished - 1 Dec 2008
Event2008 International Conference on Data Mining, DMIN 2008 - Las Vegas, NV, United States
Duration: 14 Jul 200817 Jul 2008

Other

Other2008 International Conference on Data Mining, DMIN 2008
CountryUnited States
CityLas Vegas, NV
Period14/07/0817/07/08

Fingerprint

Equivalence classes
Trees (mathematics)
Set theory
Data mining
Display devices

Keywords

  • Aprori
  • Data mining
  • Equivalence class
  • Phylogenetic trees
  • Software

Cite this

Barton, R., Zhang, S., & Herbert, K. (2008). Algorithms and software for calculating and visualizing the cardinality of the grand bounding ball by means of intersection trees. In R. Stahlbock, S. F. Crone, & S. Lessmann (Eds.), Proceedings of the 2008 International Conference on Data Mining, DMIN 2008 (pp. 529-535)
Barton, Robert ; Zhang, Sen ; Herbert, Katherine. / Algorithms and software for calculating and visualizing the cardinality of the grand bounding ball by means of intersection trees. Proceedings of the 2008 International Conference on Data Mining, DMIN 2008. editor / R. Stahlbock ; S.F. Crone ; S. Lessmann. 2008. pp. 529-535
@inproceedings{b6e82a9e76cc466daef80c44d93a1b83,
title = "Algorithms and software for calculating and visualizing the cardinality of the grand bounding ball by means of intersection trees",
abstract = "While it is straightforward to calculate the bounding ball of a partially resolved phylogenetic tree, the calculation of the cardinality of the grand bounding ball for multiple partially resolved trees is very time-consuming due to the power set principle that governs the highly iterative calculation process. What can further complicate the calculation is that the practitioner has to possess domain knowledge in phylogenetic trees, subtree mining and discrete math at the same time. This paper presents the first efficient software to automate the process of calculating the cardinality of the grand bounding ball by combining a number of advanced data mining techniques and concepts including systematically growing intersection trees, which is specially defined for this work, level by level, cluster sets, Apriori, equivalence class, and set theory, and rooting unrooted trees etc. The algorithms are discussed in the the rooted tree scope first; then they are extended to the unrooted tree scope by using a novel directing method. In addition, a displayer component has been implemented to help visualize the complicated calculation process demanded by the problem. The software is expected to be useful in phylogenetic tree clustering research.",
keywords = "Aprori, Data mining, Equivalence class, Phylogenetic trees, Software",
author = "Robert Barton and Sen Zhang and Katherine Herbert",
year = "2008",
month = "12",
day = "1",
language = "English",
isbn = "1601320620",
pages = "529--535",
editor = "R. Stahlbock and S.F. Crone and S. Lessmann",
booktitle = "Proceedings of the 2008 International Conference on Data Mining, DMIN 2008",

}

Barton, R, Zhang, S & Herbert, K 2008, Algorithms and software for calculating and visualizing the cardinality of the grand bounding ball by means of intersection trees. in R Stahlbock, SF Crone & S Lessmann (eds), Proceedings of the 2008 International Conference on Data Mining, DMIN 2008. pp. 529-535, 2008 International Conference on Data Mining, DMIN 2008, Las Vegas, NV, United States, 14/07/08.

Algorithms and software for calculating and visualizing the cardinality of the grand bounding ball by means of intersection trees. / Barton, Robert; Zhang, Sen; Herbert, Katherine.

Proceedings of the 2008 International Conference on Data Mining, DMIN 2008. ed. / R. Stahlbock; S.F. Crone; S. Lessmann. 2008. p. 529-535.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Algorithms and software for calculating and visualizing the cardinality of the grand bounding ball by means of intersection trees

AU - Barton, Robert

AU - Zhang, Sen

AU - Herbert, Katherine

PY - 2008/12/1

Y1 - 2008/12/1

N2 - While it is straightforward to calculate the bounding ball of a partially resolved phylogenetic tree, the calculation of the cardinality of the grand bounding ball for multiple partially resolved trees is very time-consuming due to the power set principle that governs the highly iterative calculation process. What can further complicate the calculation is that the practitioner has to possess domain knowledge in phylogenetic trees, subtree mining and discrete math at the same time. This paper presents the first efficient software to automate the process of calculating the cardinality of the grand bounding ball by combining a number of advanced data mining techniques and concepts including systematically growing intersection trees, which is specially defined for this work, level by level, cluster sets, Apriori, equivalence class, and set theory, and rooting unrooted trees etc. The algorithms are discussed in the the rooted tree scope first; then they are extended to the unrooted tree scope by using a novel directing method. In addition, a displayer component has been implemented to help visualize the complicated calculation process demanded by the problem. The software is expected to be useful in phylogenetic tree clustering research.

AB - While it is straightforward to calculate the bounding ball of a partially resolved phylogenetic tree, the calculation of the cardinality of the grand bounding ball for multiple partially resolved trees is very time-consuming due to the power set principle that governs the highly iterative calculation process. What can further complicate the calculation is that the practitioner has to possess domain knowledge in phylogenetic trees, subtree mining and discrete math at the same time. This paper presents the first efficient software to automate the process of calculating the cardinality of the grand bounding ball by combining a number of advanced data mining techniques and concepts including systematically growing intersection trees, which is specially defined for this work, level by level, cluster sets, Apriori, equivalence class, and set theory, and rooting unrooted trees etc. The algorithms are discussed in the the rooted tree scope first; then they are extended to the unrooted tree scope by using a novel directing method. In addition, a displayer component has been implemented to help visualize the complicated calculation process demanded by the problem. The software is expected to be useful in phylogenetic tree clustering research.

KW - Aprori

KW - Data mining

KW - Equivalence class

KW - Phylogenetic trees

KW - Software

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

M3 - Conference contribution

AN - SCOPUS:62649156842

SN - 1601320620

SN - 9781601320629

SP - 529

EP - 535

BT - Proceedings of the 2008 International Conference on Data Mining, DMIN 2008

A2 - Stahlbock, R.

A2 - Crone, S.F.

A2 - Lessmann, S.

ER -

Barton R, Zhang S, Herbert K. Algorithms and software for calculating and visualizing the cardinality of the grand bounding ball by means of intersection trees. In Stahlbock R, Crone SF, Lessmann S, editors, Proceedings of the 2008 International Conference on Data Mining, DMIN 2008. 2008. p. 529-535