Polyhedral computational geometry for averaging metric phylogenetic trees.
Saved in:
| Title: | Polyhedral computational geometry for averaging metric phylogenetic trees. |
|---|---|
| Authors: | Miller, Ezra1 ezra@math.duke.edu, Owen, Megan2 megan.owen@lehman.cuny.edu, Provan, J. Scott3 scott_provan@unc.edu |
| Source: | Advances in Applied Mathematics. Jul2015, Vol. 68, p51-91. 41p. |
| Subjects: | Polyhedra models, Computational geometry, Phylogeny, Tree graphs, Analysis of variance |
| Abstract: | This paper investigates the computational geometry relevant to calculations of the Fréchet mean and variance for probability distributions on the phylogenetic tree space of Billera, Holmes and Vogtmann, using the theory of probability measures on spaces of nonpositive curvature developed by Sturm. We show that the combinatorics of geodesics with a specified fixed endpoint in tree space are determined by the location of the varying endpoint in a certain polyhedral subdivision of tree space. The variance function associated to a finite subset of tree space has a fixed C ∞ algebraic formula within each cell of the corresponding subdivision, and is continuously differentiable in the interior of each orthant of tree space. We use this subdivision to establish two iterative methods for producing sequences that converge to the Fréchet mean: one based on Sturm's Law of Large Numbers, and another based on descent algorithms for finding optima of smooth functions on convex polyhedra. We present properties and biological applications of Fréchet means and extend our main results to more general globally nonpositively curved spaces composed of Euclidean orthants. [ABSTRACT FROM AUTHOR] |
| Copyright of Advances in Applied Mathematics is the property of Academic Press Inc. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
| FullText | Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 102659382 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Polyhedral computational geometry for averaging metric phylogenetic trees. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Miller%2C+Ezra%22">Miller, Ezra</searchLink><relatesTo>1</relatesTo><i> ezra@math.duke.edu</i><br /><searchLink fieldCode="AR" term="%22Owen%2C+Megan%22">Owen, Megan</searchLink><relatesTo>2</relatesTo><i> megan.owen@lehman.cuny.edu</i><br /><searchLink fieldCode="AR" term="%22Provan%2C+J%2E+Scott%22">Provan, J. Scott</searchLink><relatesTo>3</relatesTo><i> scott_provan@unc.edu</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Advances+in+Applied+Mathematics%22">Advances in Applied Mathematics</searchLink>. Jul2015, Vol. 68, p51-91. 41p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Polyhedra+models%22">Polyhedra models</searchLink><br /><searchLink fieldCode="DE" term="%22Computational+geometry%22">Computational geometry</searchLink><br /><searchLink fieldCode="DE" term="%22Phylogeny%22">Phylogeny</searchLink><br /><searchLink fieldCode="DE" term="%22Tree+graphs%22">Tree graphs</searchLink><br /><searchLink fieldCode="DE" term="%22Analysis+of+variance%22">Analysis of variance</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: This paper investigates the computational geometry relevant to calculations of the Fréchet mean and variance for probability distributions on the phylogenetic tree space of Billera, Holmes and Vogtmann, using the theory of probability measures on spaces of nonpositive curvature developed by Sturm. We show that the combinatorics of geodesics with a specified fixed endpoint in tree space are determined by the location of the varying endpoint in a certain polyhedral subdivision of tree space. The variance function associated to a finite subset of tree space has a fixed C ∞ algebraic formula within each cell of the corresponding subdivision, and is continuously differentiable in the interior of each orthant of tree space. We use this subdivision to establish two iterative methods for producing sequences that converge to the Fréchet mean: one based on Sturm's Law of Large Numbers, and another based on descent algorithms for finding optima of smooth functions on convex polyhedra. We present properties and biological applications of Fréchet means and extend our main results to more general globally nonpositively curved spaces composed of Euclidean orthants. [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of Advances in Applied Mathematics is the property of Academic Press Inc. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=102659382 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1016/j.aam.2015.04.002 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 41 StartPage: 51 Subjects: – SubjectFull: Polyhedra models Type: general – SubjectFull: Computational geometry Type: general – SubjectFull: Phylogeny Type: general – SubjectFull: Tree graphs Type: general – SubjectFull: Analysis of variance Type: general Titles: – TitleFull: Polyhedral computational geometry for averaging metric phylogenetic trees. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Miller, Ezra – PersonEntity: Name: NameFull: Owen, Megan – PersonEntity: Name: NameFull: Provan, J. Scott IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 07 Text: Jul2015 Type: published Y: 2015 Identifiers: – Type: issn-print Value: 01968858 Numbering: – Type: volume Value: 68 Titles: – TitleFull: Advances in Applied Mathematics Type: main |
| ResultId | 1 |
