miun.sePublications
Change search
Link to record
Permanent link

Direct link
BETA
Moulton, Vincent
Publications (10 of 23) Show all publications
Edvardsson, S., Gardner, P. P., Poole, A. M., Hendy, M. D., Penny, D. & Moulton, V. (2003). A search for H/ACA snoRNAs in yeast using MFE secondary structure prediction. Bioinformatics, 19(7), 865-873
Open this publication in new window or tab >>A search for H/ACA snoRNAs in yeast using MFE secondary structure prediction
Show others...
2003 (English)In: Bioinformatics, ISSN 1367-4803, Vol. 19, no 7, p. 865-873Article in journal (Refereed) Published
Abstract [en]

We develop an algorithm to screen the yeast genome for novel H/ACA snoRNAs. To achieve this, we introduce some new methods for facilitating the search for noncoding RNAs in genomic sequences which are based on properties of predicted minimum free-energy (MFE) secondary structures. The algorithm has been implemented and can be generalized to enable screening of other eukaryote genomes. We find that use of primary sequence alone is insufficient for identifying novel H/ACA snoRNAs. Only the use of secondary structure filters reduces the number of candidates to a manageable size. From genomic context, we identify three strong H/ACA snoRNA candidates. These together with a further 47 candidates obtained by our analysis are being experimentally screened.

Keywords
bioinformatics
National Category
Biological Sciences
Identifiers
urn:nbn:se:miun:diva-1888 (URN)10.1093/bioinformatics/btg080 (DOI)000182634800011 ()2-s2.0-003762064 (Scopus ID)700 (Local ID)700 (Archive number)700 (OAI)
Available from: 2008-09-30 Created: 2008-09-30 Last updated: 2016-10-24Bibliographically approved
Cieslik, D., Dress, A., Huber, K. T. & Moulton, V. (2003). Connectivity calculus. Applied Mathematics Letters, 16(3), 395-399
Open this publication in new window or tab >>Connectivity calculus
2003 (English)In: Applied Mathematics Letters, ISSN 0893-9659, E-ISSN 1873-5452, Vol. 16, no 3, p. 395-399Article in journal (Refereed) Published
Abstract [en]

Given a finite hypergraph H = (V, E) and, for each e E E, a collection of nonempty subsets pi(e) of e, Mobius inversion is used to establish a recursive formula for the number of connected components of the hypergraph H = (V, boolean OR(eis an element ofE)pi(e)). As shown elsewhere, this formula is an essential ingredient in the context of a certain divide-and-conquer strategy that allows us to define a dynamical programming scheme solving Steiner's problem for graphs in linear time (however, with a constant depending hyperexponentially on their tree width).

National Category
Mathematics
Identifiers
urn:nbn:se:miun:diva-13652 (URN)000181777900023 ()2-s2.0-84867985841 (Scopus ID)
Available from: 2011-04-19 Created: 2011-04-19 Last updated: 2017-12-11Bibliographically approved
Koolen, J. H. & Moulton, V. (2003). Maximal energy bipartite graphs. Graphs and Combinatorics, 19(1), 131-135
Open this publication in new window or tab >>Maximal energy bipartite graphs
2003 (English)In: Graphs and Combinatorics, ISSN 0911-0119, E-ISSN 1435-5914, Vol. 19, no 1, p. 131-135Article in journal (Refereed) Published
Abstract [en]

Given a graph G, its energy E(G) is defined to be the sum of the absolute values of the eigenvalues of G. This quantity is used in chemistry to approximate the total pi-electron energy of molecules and in particular, in case G is bipartite, alternant hydrocarbons. Here we show that if G is a bipartite graph with n vertices, thenE(G) less than or equal to n/(root8 (root2 + n)must hold, characterize those bipartite graphs for which this bound is sharp, and provide an infinite family of maximal energy bipartite graphs.Given a graph G, define the energy of G, denoted E(G), by[GRAPHICS]where the eigenvalues of, G are simply those of the adjacency matrix of G. In chemistry, the energy of a graph is intensively studied since it can be used to approximate, the total pi-electron energy of a molecule (see, for example, [3, 6, 8]). In [12], we considered maximal energy graphs (see also [9, 10, 13, 14, 17] for related results). In particular, for any graph G with n vertices, we derived an improvement of the well-known McClelland bound [15] for the energy of a graph, showing thatE(G) less than or equal to n/2(1 + rootn)must hold. We also characterized those graphs for which this bound is sharp, i.e. the maximal energy graphs, and provided an infinite family of such graphs.

National Category
Mathematics
Identifiers
urn:nbn:se:miun:diva-13646 (URN)10.1007/s00373-002-0487-7 (DOI)000182689700009 ()2-s2.0-0038238082 (Scopus ID)
Available from: 2011-04-19 Created: 2011-04-19 Last updated: 2017-12-11Bibliographically approved
Dress, A., Huber, K. T. & Moulton, V. (2002). An explicit computation of the injective hull of certain finite metric spaces in terms of their associated Buneman complex. Advances in Mathematics, 168(1), 1-28
Open this publication in new window or tab >>An explicit computation of the injective hull of certain finite metric spaces in terms of their associated Buneman complex
2002 (English)In: Advances in Mathematics, ISSN 0001-8708, E-ISSN 1090-2082, Vol. 168, no 1, p. 1-28Article in journal (Refereed) Published
Keywords
Matematik
National Category
Mathematics
Identifiers
urn:nbn:se:miun:diva-13658 (URN)10.1006/aima.2001.2039 (DOI)000176243700001 ()2-s2.0-0036608690 (Scopus ID)
Available from: 2011-04-20 Created: 2011-04-20 Last updated: 2017-12-11Bibliographically approved
Dress, A., Huber, K. T. & Moulton, V. (2002). Antipodal metrics and split systems. European journal of combinatorics (Print), 23(2), 187-200
Open this publication in new window or tab >>Antipodal metrics and split systems
2002 (English)In: European journal of combinatorics (Print), ISSN 0195-6698, E-ISSN 1095-9971, Vol. 23, no 2, p. 187-200Article in journal (Refereed) Published
Abstract [en]

Recall that a metric d on a finite set X is called antipodal if there exists a map sigma : X --> X: x --> (x) over bar so that d(x, (x) over bar) = d(x, y) + d(y, (x) over bar) holds for all x, y epsilon X. Antipodal metrics canonically arise as metrics induced on specific weighted graphs, although their abundance becomes clearer in light of the fact that any finite metric space can be isometrically embedded in a more or less canonical way into an antipodal metric space called its full antipodal extension. In this paper, we examine in some detail antipodal metrics that are, in addition, totally split decomposable. In particular, we give an explicit characterization of such metrics, and prove that-somewhat surprisingly-the full antipodal extension of a proper metric d on a finite set X is totally split decomposable if and only if d is linear or #X = 3 holds.

National Category
Mathematics
Identifiers
urn:nbn:se:miun:diva-13674 (URN)10.1006/eujc.2001.0556 (DOI)000173869900005 ()2-s2.0-0036110215 (Scopus ID)
Available from: 2011-04-21 Created: 2011-04-21 Last updated: 2017-12-11Bibliographically approved
Koolen, J. H. & Moulton, V. (2002). Hyperbolic bridged graphs. European journal of combinatorics (Print), 23(6), 683-699
Open this publication in new window or tab >>Hyperbolic bridged graphs
2002 (English)In: European journal of combinatorics (Print), ISSN 0195-6698, E-ISSN 1095-9971, Vol. 23, no 6, p. 683-699Article in journal (Refereed) Published
Abstract [en]

Given a connected graph G, we take, as usual, the distance xy between any two vertices x, y of G to be the length of some geodesic between x and y. The graph G is said to be delta-hyperbolic, for some 3 : 0, if for all vertices x, y, u, v in G the inequality xy + uv :5 max{xu + yv, xv + yu} + delta holds, and G is bridged if it contains no finite isometric cycles of length four or more. In this paper, we will show that a finite connected bridged graph is 1-hyperbolic if and only if it does not contain any of a list of six graphs as an isometric subgraph.

Identifiers
urn:nbn:se:miun:diva-13629 (URN)10.1006/eujc.2002.0591 (DOI)000178136300005 ()
Available from: 2011-04-19 Created: 2011-04-19 Last updated: 2017-12-11Bibliographically approved
Dress, A., Koolen, J. H. & Moulton, V. (2002). On line arrangements in the hyperbolic plane. European journal of combinatorics (Print), 23(5), 549-557
Open this publication in new window or tab >>On line arrangements in the hyperbolic plane
2002 (English)In: European journal of combinatorics (Print), ISSN 0195-6698, E-ISSN 1095-9971, Vol. 23, no 5, p. 549-557Article in journal (Refereed) Published
Abstract [en]

Given a finite collection L of lines in the hyperbolic plane H, we denote by k = k(L) its Karzanov number, i.e., the maximal number of pairwise intersecting lines in L, and by C(L) and n = n(L) the set and the number, respectively, of those points at infinity that are incident with at least one line from L. By using purely combinatorial properties of cyclic seta:, it is shown that #L less than or equal to 2nk - ((2k+1)(2)) always holds and that #L equals 2nk - ((2k+1)(2)) if and only if there is no collection L' of lines in H with L subset of or equal to L', k(L') = k(L) and C(L') = C(L).

National Category
Mathematics
Identifiers
urn:nbn:se:miun:diva-13627 (URN)10.1006/eujc.2002.0582 (DOI)000178540300008 ()2-s2.0-0036382989 (Scopus ID)
Available from: 2011-04-19 Created: 2011-04-19 Last updated: 2017-12-11Bibliographically approved
Bandelt, H. J., Huber, K. T. & Moulton, V. (2002). Quasi-median graphs from sets of partitions. Discrete Applied Mathematics, 122(1-3), 23-35
Open this publication in new window or tab >>Quasi-median graphs from sets of partitions
2002 (English)In: Discrete Applied Mathematics, ISSN 0166-218X, E-ISSN 1872-6771, Vol. 122, no 1-3, p. 23-35Article in journal (Refereed) Published
Abstract [en]

In studies of molecular evolution, one is typically confronted with the task of inferring a phylogenetic tree from a set X of sequences of length n over a finite alphabet Λ. For studies that invoke parsimony, it has been found helpful to consider the quasi-median graph generated by X in the Hamming graph Λn. Although a great deal is already known about quasi-median graphs (and their algebraic counterparts), little is known about the quasi-median generation in Λn starting from a set X of vertices. We describe the vertices of the quasi-median graph generated by X in terms of the coordinatewise partitions of X. In particular, we clarify when the generated quasi-median graph is the so-called relation graph associated with X. This immediately characterizes the instances where either a block graph or the total Hamming graph is generated. 

National Category
Mathematics
Identifiers
urn:nbn:se:miun:diva-8434 (URN)10.1016/S0166-218X(01)00353-5 (DOI)000176416200003 ()2-s2.0-84867954486 (Scopus ID)
Available from: 2009-01-25 Created: 2009-01-25 Last updated: 2017-12-14Bibliographically approved
Huber, K. T. & Moulton, V. (2002). The relation graph. Paper presented at 4th Slovenian Graph Theory Conference BLED, SLOVENIA, JUN 28-JUL 02, 1999. Discrete Mathematics, 244(1-3), 153-166
Open this publication in new window or tab >>The relation graph
2002 (English)In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 244, no 1-3, p. 153-166Article in journal (Refereed) Published
Abstract [en]

Given a set R of distinct, non-trivial partitions of a finite set, we define the relation graph G(R) of R. In case R consists only of bipartitions, G(R) is the well-known Buneman graph, a median graph that has applications in the area of phylogenetic analysis., Here we consider properties of the relation graph for general sets of partitions and, in particular, we see that it mimics the behaviour of the Buneman graph by proving the following two theorems:(i) The graph G(R) is a Hamming graph if and only if R is strongly incompatible.(ii) The graph G(R) is a block graph with #R blocks if and only if R is strongly compatible.

National Category
Mathematics
Identifiers
urn:nbn:se:miun:diva-13675 (URN)10.1016/S0012-365X(01)00080-2 (DOI)000173839800015 ()2-s2.0-31244433852 (Scopus ID)
Conference
4th Slovenian Graph Theory Conference BLED, SLOVENIA, JUN 28-JUL 02, 1999
Note

4th Slovenian Graph Theory Conference, Jun 28-Jul 02, 1999, Bled, Slovenia

Available from: 2011-04-21 Created: 2011-04-21 Last updated: 2017-12-11Bibliographically approved
Koolen, J. H. & Moulton, V. (2001). Maximal energy graphs. Advances in Applied Mathematics, 26(1), 47-52
Open this publication in new window or tab >>Maximal energy graphs
2001 (English)In: Advances in Applied Mathematics, ISSN 0196-8858, E-ISSN 1090-2074, Vol. 26, no 1, p. 47-52Article in journal (Refereed) Published
Abstract [en]

Given a graph G, its energy E(G) is defined as the sum of the absolute values of the eigenvalues of G. The concept of the energy of a graph was introduced in the subject of chemistry by I. Gutman. due to its relevance to the total pi -elrctron energy of certain molecules. In this paper, we show that if G is a graph on n vertices, then E(G) less than or equal to (n/2)(1 + rootn) must hold, and we give an infinite family of graphs for which this bound is sharp.

National Category
Computational Mathematics
Identifiers
urn:nbn:se:miun:diva-13608 (URN)10.1006/aama.2000.0705 (DOI)000166366300003 ()2-s2.0-0035217286 (Scopus ID)
Available from: 2011-04-19 Created: 2011-04-19 Last updated: 2017-12-11Bibliographically approved
Organisations

Search in DiVA

Show all publications