All galls are divided into three or more parts: recursive enumeration of labeled histories for galled trees

Algorithms for Molecular Biology

Research

Shaili Mathur¹  Noah A. Rosenberg¹ 

[1] Department of Biology, Stanford University, 94305, Stanford, CA, USA;

关键词: Galled trees;    Labeled histories;    Mathematical phylogenetics;    Phylogenetic networks;   

DOI  :  10.1186/s13015-023-00224-4

 received in 2022-09-13, accepted in 2023-01-27,  发布年份 2023

来源: Springer

【 摘 要 】

ObjectiveIn mathematical phylogenetics, a labeled rooted binary tree topology can possess any of a number of labeled histories, each of which represents a possible temporal ordering of its coalescences. Labeled histories appear frequently in calculations that describe the combinatorics of phylogenetic trees. Here, we generalize the concept of labeled histories from rooted phylogenetic trees to rooted phylogenetic networks, specifically for the class of rooted phylogenetic networks known as rooted galled trees.ResultsExtending a recursive algorithm for enumerating the labeled histories of a labeled tree topology, we present a method to enumerate the labeled histories associated with a labeled rooted galled tree. The method relies on a recursive decomposition by which each gall in a galled tree possesses three or more descendant subtrees. We exhaustively provide the numbers of labeled histories for all small galled trees, finding that each gall reduces the number of labeled histories relative to a specified galled tree that does not contain it.ConclusionThe results expand the set of structures for which labeled histories can be enumerated, extending a well-known calculation for phylogenetic trees to a class of phylogenetic networks.

【 授权许可】

CC BY   
© The Author(s) 2023

【 图 表 】

Fig. 7

Fig. 1

Fig. 1

Fig. 10

Fig. 5

40708_2023_184_Article_IEq4.gif

Fig. 5

Fig. 8

Fig. 4

Fig. 6

Fig. 4

Fig. 3

Fig. 2

Fig. 1

Fig. 5

40854_2022_419_Article_IEq15.gif

Fig. 6

Fig. 3

Fig. 2

Fig. 2

Fig. 1

Fig. 5

Fig. 2

Fig. 4

40854_2023_456_Article_IEq31.gif

Fig. 1

Fig. 2

40854_2022_419_Article_IEq5.gif

Fig. 4

Fig. 5

40517_2023_248_Article_IEq41.gif

40517_2023_248_Article_IEq40.gif

40517_2023_248_Article_IEq37.gif

Fig. 1

40517_2023_248_Article_IEq35.gif

40517_2023_248_Article_IEq34.gif

40517_2023_248_Article_IEq33.gif

Fig. 4

40517_2023_248_Article_IEq31.gif

40517_2023_248_Article_IEq30.gif

40517_2023_248_Article_IEq29.gif

40517_2023_248_Article_IEq28.gif

40517_2023_248_Article_IEq25.gif

40517_2023_248_Article_IEq24.gif

40854_2023_456_Article_IEq6.gif

40517_2023_248_Article_IEq23.gif

40517_2023_248_Article_IEq22.gif

40517_2023_248_Article_IEq21.gif

40517_2023_248_Article_IEq20.gif

40517_2023_248_Article_IEq19.gif

40517_2023_248_Article_IEq17.gif

40517_2023_248_Article_IEq16.gif

40517_2023_248_Article_IEq15.gif

40517_2023_248_Article_IEq14.gif

40517_2023_248_Article_IEq13.gif

40517_2023_248_Article_IEq12.gif

40517_2023_248_Article_IEq10.gif

40517_2023_248_Article_IEq9.gif

40517_2023_248_Article_IEq7.gif

40517_2023_248_Article_IEq5.gif

40517_2023_248_Article_IEq3.gif

40517_2023_248_Article_IEq2.gif

40517_2023_248_Article_IEq1.gif

Fig. 9

Fig. 1

Fig. 13

Fig. 12

12936_2023_4464_Article_IEq13.gif

Fig. 2

Fig. 5

Fig. 11

Fig. 1

Fig. 10

40854_2023_460_Article_IEq15.gif

12936_2023_4464_Article_IEq7.gif

Fig. 9

Fig. 4

Fig. 1

Fig. 7

Fig. 3

Fig. 13

Fig. 7

Fig. 6

Fig. 1

Fig. 1

Fig. 2

Fig. 1

Fig. 5

Fig. 1

Fig. 12

Fig. 2

Fig. 4

Fig. 1

Fig. 2

Fig. 8

Fig. 4

Fig. 2

Fig.1

Fig. 1

Fig. 2

Fig. 3

13690_2023_1046_Article_IEq7.gif

Fig. 3

13690_2023_1046_Article_IEq4.gif

Fig. 5

Fig. 8

Fig. 1

13690_2023_1046_Article_IEq1.gif

Fig. 4

Fig. 2

Fig. 7

Fig. 2

Fig. 1

Fig. 6

Fig. 1

Fig. 7

Fig. 1

12936_2023_4470_Article_IEq1.gif

Fig. 5

Fig. 6

Fig. 1

Fig. 5

Fig. 2

Fig. 6

Fig. 4

Fig. 9

Fig. 3

Fig. 3

Fig. 2

Fig. 5

Fig. 8

Fig. 5

Fig. 7

Fig. 5

Fig. 2

Fig. 4

Fig. 1

Fig. 4

Fig. 4

Fig. 6

Fig. 1

Fig. 3

Fig. 2

Fig. 5

42004_2023_824_Taba_HTML.png

Fig. 3

Fig. 6

Fig. 1

Fig. 2

Fig. 3

Fig. 1

Fig. 4

Fig. 7

Fig. 1

Fig. 2

Fig. 2

Fig. 1

Fig. 2

Fig. 2

Fig. 1

Fig. 5

Fig. 1

Fig. 2

Fig. 4

Fig. 3

40854_2022_440_Article_IEq31.gif

Fig. 1

Fig. 2

Fig. 2

Fig. 6

Fig. 4

Fig. 4

Fig. 2

Fig. 2

Fig. 2

Fig. 3

Fig. 2

Fig. 2

Fig. 8

Fig. 1

Fig. 1

Fig. 4

Fig. 1

Fig. 3

Fig. 1

Fig. 9

Fig. 1

Fig. 1

Fig. 2

Fig. 22

Fig. 1

Fig. 4

Fig. 2

Fig. 1

Fig. 7

40854_2022_440_Article_IEq23.gif

Fig. 1

Fig. 2

Fig. 8

Fig. 3

Fig. 4

40854_2022_440_Article_IEq15.gif

Fig. 7

Fig. 1

Fig. 6

Fig. 2

Fig. 3

Fig. 1

Fig. 2

Fig. 5

Fig. 1

Fig. 1

Fig. 4

Fig. 2

Fig. 5

Fig. 5

Fig. 1

Fig. 2

13690_2023_1037_Article_IEq1.gif

Fig. 4

40708_2023_185_Article_IEq64.gif

Fig. 2

Fig. 3