✦ LIBER ✦

Enumerating phylogenetic trees with multiple labels

✍ Scribed by L.R. Foulds; R.W. Robinson

Publisher: Elsevier Science
Year: 1988
Tongue: English
Weight: 524 KB
Volume: 72
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(88)90201-4

No coin nor oath required. For personal study only.

✦ Synopsis

Evolutionary

trees are used in biology to illustrate postulated ancestral relationships between species and are often called phylogenetic trees. They can be characterized in graph theoretic terms by certain classes of labelled trees. Disjoint subsets of the labelling set are assigned to tree vertices so that all pendant vertices and any vertices of degree two are labelled.

Here we determine exact and asymptotic numbers for two classes of trees in which multiple vertex labels are allowed.

In the first class vertices of degree two are forbidden and in the second class vertices of degree greater than two cannot be labelled.

A general method is presented for deriving the asymptotic analysis of any multiple label case. Asymptotic results for the two classes of trees under study are then obtained by applying this method to previously published results.

📜 SIMILAR VOLUMES

Enumeration of Labelled (k, m)-Tree

Enumeration of Labelled (k, m)-Trees

✍ Oleg Pikhurko 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 78 KB

A k-graph is called a (k, m)-tree if it can be obtained from a single edge by consecutively adding edges so that every new edge contains k&m new vertices while its remaining m vertices are covered by an already existing edge. We prove that there are (e(k&m)+m)!(e( k m )&e+1) e&2 e!m!((k&m)!) e disti

Exact Enumeration of 1342-Avoiding Permu

Exact Enumeration of 1342-Avoiding Permutations: A Close Link with Labeled Trees and Planar Maps

✍ Miklós Bóna 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 318 KB

Solving the first nonmonotonic, longer-than-three instance of a classic enumeration problem, we obtain the generating function H(x) of all 1342-avoiding permutations of length n as well as an exact formula for their number S n (1342). While achieving this, we bijectively prove that the number of ind

The enumeration of trees with and withou

The enumeration of trees with and without given limbs

✍ Taojun Lu 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 720 KB

A limb of a tree is the union of one or more branches at a vertex in the tree, where a branch of a tree at a vertex is a maximal subtree containing the given vertex as an end-vertex. In this note, we first consider the enumeration of trees (undirected, oriented or mixed) with forbidden limbs. The en

Graph-based semi-supervised learning wit

Graph-based semi-supervised learning with multiple labels

✍ Zheng-Jun Zha; Tao Mei; Jingdong Wang; Zengfu Wang; Xian-Sheng Hua 📂 Article 📅 2009 🏛 Elsevier Science 🌐 English ⚖ 328 KB

Enumeration of basic kinetic chains with

Enumeration of basic kinetic chains with simple and multiple joints

✍ Cheng-Ho Hsu 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 801 KB

This paper presents a simple method, based on the concept of contracted graphs, for the enumeration of basic kinematic chains with simple and multiple joints. AN possible acceptable contracted graphs are listed according to the numbers of links and degrees of freedom of basic kinematic chains. Next,

Bipartite labeling of trees with maximum

Bipartite labeling of trees with maximum degree three

✍ Bonnington, C. Paul; ?ir�?, Jozef 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 258 KB 👁 3 views

Let T = (V, E) be a tree with a properly 2-colored vertex set. A bipartite labeling of T is a bijection ϕ: V → {1, . . . , |V |} for which there exists a k such that whenever ϕ(u) ≤ k < ϕ(v), then u and v have different colors. The α-size α(T ) of the tree T is the maximum number of elements in the