DC Field | Value | Language |
---|---|---|
dc.contributor.author | Dress, A | - |
dc.contributor.author | Holland, B | - |
dc.contributor.author | Huber, KT | - |
dc.contributor.author | Koolen, JH | - |
dc.contributor.author | Moulton, V | - |
dc.contributor.author | Weyer-Menkhoff, J | - |
dc.date.accessioned | 2016-04-01T08:16:09Z | - |
dc.date.available | 2016-04-01T08:16:09Z | - |
dc.date.created | 2010-02-12 | - |
dc.date.issued | 2005-02-15 | - |
dc.identifier.issn | 0166-218X | - |
dc.identifier.other | 2005-OAK-0000019860 | - |
dc.identifier.uri | https://oasis.postech.ac.kr/handle/2014.oak/27595 | - |
dc.description.abstract | In phylogenetic analysis. one searches for phylogenetic trees that reflect observed similarity between a collection of species in question. To this end. one often invokes two simple facts: (i) Any tree is completely determined by the metric it induces on its leaves (which represent the species). (ii) The resulting metrics are characterized by their property of being additive or in the case of dated rooted trees, ultra-additive. Consequently, searching for additive or ultra-additive metrics A that best approximate the metric D encoding the observed similarities is a standard task in phylogenetic analysis. Remarkably, while there are efficient algorithms for constructing optimal ultra-additive approximations, the problem of finding optimal additive approximations in the l(I) or l(infinity) sense is NP-hard. In the context of the theory of delta-hyperbolic groups, however, good additive approximations A of a metric D were found by Gromov already in 1988 and shown to satisfy the bound parallel toD - Aparallel toinfinity less than or equal to Delta(D)[log(2)(#X - 1)]. where Delta(D), the hyperbolicity of D, i.e. the maximum of all expressions of the form D (u, v) + D (x, y) - max (D(u, x) + D (v, y), D(u, y) + D (v, x)) (u, v, x, y is an element of X). Yet, besides some notable exceptions (e.g. Adv. Appl. Math. 27 (2001) 733-767) the potential of Gromov's concept of hyperbolicity is far from being fully explored within the context of phylogenetic analysis. In this paper, we provide the basis for a systematic theory of A ultra-additive and A additive approximations. In addition. we also explore, the average and worst case behavior of Gromov's bound. (C) 2004 Elsevier B.V. All rights reserved. | - |
dc.description.statementofresponsibility | X | - |
dc.language | English | - |
dc.publisher | elsevier | - |
dc.relation.isPartOf | Discrete Applied Mathematics | - |
dc.subject | additive maps | - |
dc.subject | ultra-additive maps | - |
dc.subject | additive trees | - |
dc.subject | ultrametrics | - |
dc.subject | delta-hyperbolic metrics | - |
dc.subject | hyperbolicity | - |
dc.subject | l infinity-approximations | - |
dc.subject | Farris transform | - |
dc.subject | T-theory | - |
dc.subject | STATISTICAL GEOMETRY | - |
dc.subject | METRIC-SPACES | - |
dc.title | Δ additive and Δ ultra-additive maps, Gromov's trees, and the Farris transform | - |
dc.type | Article | - |
dc.contributor.college | 수학과 | - |
dc.identifier.doi | 10.1016/j.dam.2003.01.003 | - |
dc.author.google | Dress, A | - |
dc.author.google | Holland, B | - |
dc.author.google | Huber, KT | - |
dc.author.google | Koolen, JH | - |
dc.author.google | Moulton V | - |
dc.author.google | Weyer-Menkhoff, J | - |
dc.relation.volume | 146 | - |
dc.relation.issue | 1 | - |
dc.relation.startpage | 51 | - |
dc.relation.lastpage | 73 | - |
dc.contributor.id | 10200295 | - |
dc.relation.journal | Discrete Applied Mathematics | - |
dc.relation.index | SCI급, SCOPUS 등재논문 | - |
dc.relation.sci | SCI | - |
dc.collections.name | Journal Papers | - |
dc.type.rims | ART | - |
dc.identifier.bibliographicCitation | Discrete Applied Mathematics, v.146, no.1, pp.51 - 73 | - |
dc.identifier.wosid | 000226524500005 | - |
dc.date.tcdate | 2019-02-01 | - |
dc.citation.endPage | 73 | - |
dc.citation.number | 1 | - |
dc.citation.startPage | 51 | - |
dc.citation.title | Discrete Applied Mathematics | - |
dc.citation.volume | 146 | - |
dc.contributor.affiliatedAuthor | Koolen, JH | - |
dc.description.journalClass | 1 | - |
dc.description.journalClass | 1 | - |
dc.description.wostc | 13 | - |
dc.type.docType | Article | - |
dc.subject.keywordAuthor | additive maps | - |
dc.subject.keywordAuthor | ultra-additive maps | - |
dc.subject.keywordAuthor | additive trees | - |
dc.subject.keywordAuthor | ultrametrics | - |
dc.subject.keywordAuthor | delta-hyperbolic metrics | - |
dc.subject.keywordAuthor | hyperbolicity | - |
dc.subject.keywordAuthor | l infinity-approximations | - |
dc.subject.keywordAuthor | Farris transform | - |
dc.subject.keywordAuthor | T-theory | - |
dc.relation.journalWebOfScienceCategory | Mathematics, Applied | - |
dc.description.journalRegisteredClass | scie | - |
dc.description.journalRegisteredClass | scopus | - |
dc.relation.journalResearchArea | Mathematics | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
library@postech.ac.kr Tel: 054-279-2548
Copyrights © by 2017 Pohang University of Science ad Technology All right reserved.