Timeline for Enumerating unlabeled phylogenetic trees
Current License: CC BY-SA 4.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 25, 2022 at 10:34 | vote | accept | Daniel Geisler | ||
| Aug 25, 2022 at 10:24 | comment | added | Szabolcs | Related, as it deals with constraints on the degrees of internal vertices: mathematica.stackexchange.com/q/234476/12 | |
| Aug 25, 2022 at 10:23 | comment | added | Szabolcs | That makes sense but this should be clarified in the post. | |
| Aug 25, 2022 at 9:12 | comment | added | Lacia | @Szabolcs To my understanding, the phylogenetic tree mentioned by OP contains no nodes with degree=2 except the root, and here $n$ is the number of leaves. | |
| Aug 25, 2022 at 8:58 | answer | added | Lacia | timeline score: 1 | |
| Aug 24, 2022 at 11:09 | comment | added | Szabolcs |
For your convenience, implementation using my IGraph/M package: Function[n, Catenate[ Function[tree, DeleteDuplicatesBy[IGOrientTree[tree, #] & /@ VertexList[tree], CanonicalGraph]] /@ IGImport[ "!/opt/local/bin/geng " <> IntegerString[n] <> " " <> IntegerString[n - 1] <> " -c", "Nauty"]]] Remember to edit the path to geng for your system.
|
|
| Aug 24, 2022 at 11:08 | comment | added | Szabolcs | Getting directed trees from this is not entirely trivial. For each undirected tree, we can orient edges away from each vertex, obtaining $n$ directed trees. However, some of these will still be isomorphic, and will need to be filtered out. With this method, I get this for 4 vertices: i.sstatic.net/fc8B8.png These are 4 trees, but you claim 5. What is missing? There are no other directed out-trees on 4 vertices, only these. | |
| Aug 24, 2022 at 10:59 | comment | added | Szabolcs |
If we only wanted to generate unlabelled undirected trees, we could use the geng utility from the nauty suite. It can generate all unlabelled graphs with $n$ vertices and $m$ edges, with certain constraints. If we want trees, we can ask for connceted graphs with $n$ vertices and $n-1$ edges. For example, with $n=7$, use Import["!geng 7 6 -c", "Graph6"]. You may need to put the absolute path to geng for your system.
|
|
| Aug 24, 2022 at 10:55 | comment | added | Szabolcs | Also, what do you mean by "enumerating"? Do you mean merely counting (the word is sometimes used in this sense in math) or generating each and every instance (which is the more general meaning)? | |
| Aug 24, 2022 at 10:54 | comment | added | Szabolcs | Can you clarify what a "phylogenetic tree" means in this context? I assume it means a rooted tree, which can be encoded as a directed tree with edges oriented away from the root? Is your problem equivalent to finding all non-isomorphic directed trees on $n$ vertices? | |
| S Aug 24, 2022 at 7:56 | review | First questions | |||
| Aug 24, 2022 at 18:45 | |||||
| S Aug 24, 2022 at 7:56 | history | asked | Daniel Geisler | CC BY-SA 4.0 |
