Decision tree SAR models for developmental toxicity based on an FDA/TERIS database

Humans are exposed to thousands of environmental chemicals for which no developmental toxicity information is available. Structure-activity relationships (SARs) are models that could be used to efficiently predict the biological activity of potential developmental toxicants. However, at this time, no adequate SAR models of developmental toxicity are available for risk assessment. In the present study, a new developmental database was compiled by combining toxicity information from the Teratogen Information System (TERIS) and the Food and Drug Administration (FDA) guidelines. We implemented a decision tree modeling procedure, using Classification and Regression Tree software and a model ensemble approach termed bagging. We then assessed the empirical distributions of the prediction accuracy measures of the single and ensemble-based models, achieved by repeating our modeling experiment many times by repeated random partitioning of the working database. The decision tree developmental SAR models exhibited modest prediction accuracy. Bagging tended to enhance the accuracy of prediction. Also, the model ensemble approach reduced the variability of prediction measures compared to the single model approach. Further research with data derived from animal species- and endpoint-specific components of an extended and refined FDA/TERIS database has the potential to derive SAR models that would be useful in the developmental risk assessment of the thousands of untested chemicals.     

Colouring graphs with bounded generalized colouring number

Given a graph G and a positive integer p, χ_p(G) is the minimum number of colours needed to colour the vertices of G so that for any i≤p, any subgraph H of G of tree-depth i gets at least i colours. This paper proves an upper bound for χ_p(G) in terms of the k-colouring number of G for k=2^p−2. Conversely, for each integer k, we also prove an upper bound for in terms of χ_k+2(G). As a consequence, for a class K of graphs, the following two statements are equivalent:

(a)

For every positive integer p, χ_p(G) is bounded by a constant for all G∈K.

(b)

For every positive integer k, is bounded by a constant for all G∈K.

It was proved by Nešet?il and Ossona de Mendez that (a) is equivalent to the following:

(c)

For every positive integer q, ∇_q(G) (the greatest reduced average density of G with rank q) is bounded by a constant for all G∈K.

Therefore (b) and (c) are also equivalent. We shall give a direct proof of this equivalence, by introducing ∇_q−(1/2)(G) and by showing that there is a function F_k such that . This gives an alternate proof of the equivalence of (a) and (c).     

On the shape of decomposable trees

A n-vertex graph is said to be decomposable if, for any partition (λ₁,…,λ_p) of the integer n, there exists a sequence (V₁,…,V_p) of connected vertex-disjoint subgraphs with |V_i|=λ_i. The aim of the paper is to study the homeomorphism classes of decomposable trees. More precisely, we show that homeomorphism classes containing decomposable trees with an arbitrarily large minimal distance between all pairs of distinct vertices of degree different from 2, is exactly the set of combs.     

The parameterized complexity of the induced matching problem

Given a graph G and an integer k≥0, the NP-complete Induced Matching problem asks whether there exists an edge subset M of size at least k such that M is a matching and no two edges of M are joined by an edge of G. The complexity of this problem on general graphs, as well as on many restricted graph classes has been studied intensively. However, other than the fact that the problem is W[1]-hard on general graphs, little is known about the parameterized complexity of the problem in restricted graph classes. In this work, we provide first-time fixed-parameter tractability results for planar graphs, bounded-degree graphs, graphs with girth at least six, bipartite graphs, line graphs, and graphs of bounded treewidth. In particular, we give a linear-size problem kernel for planar graphs.     

Computing bounded-degree phylogenetic roots of disconnected graphs

The Phylogenetic kth Root Problem (PRk) is the problem of finding a (phylogenetic) tree T from a given graph G=(V,E) such that (1) T has no degree-2 internal nodes, (2) the external nodes (i.e., leaves) of T are exactly the elements of V, and (3) (u,v)E if and only if the distance between u and v in tree T is at most k, where k is some fixed threshold k. Such a tree T, if exists, is called a phylogenetic kth root of graph G. The computational complexity of PRk is open, except for k4. Recently, Chen et al. investigated PRk under a natural restriction that the maximum degree of the phylogenetic root is bounded from above by a constant. They presented a linear-time algorithm that determines if a given connected G has such a phylogenetic kth root, and if so, demonstrates one. In this paper, we supplement their work by presenting a linear-time algorithm for disconnected graphs.     

Labeling trees with a condition at distance two

An L(h,k)-labeling of a graph G is an integer labeling of vertices of G, such that adjacent vertices have labels which differ by at least h, and vertices at distance two have labels which differ by at least k. The span of an L(h,k)-labeling is the difference between the largest and the smallest label. We investigate L(h,k)-labelings of trees of maximum degree Δ, seeking those with small span. Given Δ, h and k, span λ is optimal for the class of trees of maximum degree Δ, if λ is the smallest integer such that every tree of maximum degree Δ has an L(h,k)-labeling with span at most λ. For all parameters Δ,h,k, such that h<k, we construct L(h,k)-labelings with optimal span. We also establish optimal span of L(h,k)-labelings for stars of arbitrary degree and all values of h and k.     

A linear algorithm for minimum 1-identifying codes in oriented trees

Consider an oriented graph G=(V,A), a subset of vertices C⊆V, and an integer r?1; for any vertex v∈V, let denote the set of all vertices x such that there exists a path from x to v with at most r arcs. If for all vertices v∈V, the sets are all nonempty and different, then we call C an r-identifying code. We describe a linear algorithm which gives a minimum 1-identifying code in any oriented tree.     

Vertex-transitive expansions of (1, 3)-trees

A nonidentity automorphism of a graph is said to be semiregular if all of its orbits are of the same length. Given a graph X with a semiregular automorphism γ, the quotient of X relative to γ is the multigraph X/γ whose vertices are the orbits of γ and two vertices are adjacent by an edge with multiplicity r if every vertex of one orbit is adjacent to r vertices of the other orbit. We say that X is an expansion of X/γ. In [J.D. Horton, I.Z. Bouwer, Symmetric Y-graphs and H-graphs, J. Combin. Theory Ser. B 53 (1991) 114-129], Horton and Bouwer considered a restricted sort of expansions (which we will call ‘strong’ in this paper) where every leaf of X/γ expands to a single cycle in X. They determined all cubic arc-transitive strong expansions of simple (1, 3)-trees, that is, trees with all of their vertices having valency 1 or 3, thus extending the classical result of Frucht, Graver and Watkins (see [R. Frucht, J.E. Graver, M.E. Watkins, The groups of the generalized Petersen graphs, Proc. Cambridge Philos. Soc. 70 (1971) 211-218]) about arc-transitive strong expansions of K₂ (also known as the generalized Petersen graphs). In this paper another step is taken further by considering the possible structure of cubic vertex-transitive expansions of general (1,3)-multitrees (where vertices with double edges are also allowed); thus the restriction on every leaf to be expanded to a single cycle is dropped.