Rolf Fagerberg

Rolf Fagerberg

Auto-generated profile, based on publicly available information

Rolf Fagerberg

Department of Mathematics and Computer Science, University of Southern Denmark, DK-5230 Odense M, Denmark

Research Focus & Metrics

Academic Career Length

23Years (2004-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
19 January 2006 in BMC Bioinformatics
Verified
Journal Article
Open access
PDF file
TMThomas Mailund
Thomas Mailund
GBGerth S Brodal
Gerth S Brodal
RFRolf Fagerberg
Rolf Fagerberg
CPChristian Ns Pedersen
Christian Ns Pedersen
DPDerek Phillips
Derek Phillips
Background: The neighbor-joining method by Saitou and Nei is a widely used method for constructing phylogenetic trees. The formulation of the method gives rise to a canonical Θ(n3) algorithm upon which all existing implementations are based.Results: In this paper we present techniques for speeding up the canonical neighbor-joining method. Our algorithms construct the same phylogenetic trees as the canonical neighbor-joining method. The best-case running time of our algorithms areO(n2) but the worst-case remainsO(n3). We empirically evaluate the performance of our algoritms on distance matrices obtained from the Pfam collection of alignments. The experiments indicate that the running time of our algorithms evolve as Θ(n2) on the examined instance collection. We also compare the running time with that of the QuickTree tool, a widely used efficient implementation of the canonical neighbor-joining method.Conclusion: The experiments show that our algorithms also yield a significant speed-up, already for medium sized instances.

18 November 2017 in Annals of Operations Research
Verified
Journal Article
Closed access
PDF file
MCMarco Chiarandini
Marco Chiarandini
RFRolf Fagerberg
Rolf Fagerberg
SGStefano Gualandi
Stefano Gualandi

26 August 2010 in Theory of Computing Systems
Verified
Journal Article
Closed access
PDF file
MBMichael A. Bender
Michael A. Bender
GBGerth Stølting Brodal
Gerth Stølting Brodal
RFRolf Fagerberg
Rolf Fagerberg
RJRiko Jacob
Riko Jacob
EVElias Vicari
Elias Vicari

5 April 2018 in Journal of Cheminformatics
Verified
Journal Article
Open access
PDF file
RFRolf Fagerberg
Rolf Fagerberg
CFChristoph Flamm
Christoph Flamm
RKRojin Kianian
Rojin Kianian
DMDaniel Merkle
Daniel Merkle
Peter F. StadlerPeter F. Stadler
Peter F. Stadler
In synthesis planning, the goal is to synthesize a target molecule from available starting materials, possibly optimizing costs such as price or environmental impact of the process. Current algorithmic approaches to synthesis planning are usually based on selecting a bond set and finding a single good plan among those induced by it. We demonstrate that synthesis planning can be phrased as a combinatorial optimization problem on hypergraphs by modeling individual synthesis plans as directed hyperpaths embedded in a hypergraph of reactions (HoR) representing the chemistry of interest. As a consequence, a polynomial time algorithm to find the K shortest hyperpaths can be used to compute the K best synthesis plans for a given target molecule. Having K good plans to choose from has many benefits: it makes the synthesis planning process much more robust when in later stages adding further chemical detail, it allows one to combine several notions of cost, and it provides a way to deal with imprecise yield estimates. A bond set gives rise to a HoR in a natural way. However, our modeling is not restricted to bond set based approaches—any set of known reactions and starting materials can be used to define a HoR. We also discuss classical quality measures for synthesis plans, such as overall yield and convergency, and demonstrate that convergency has a built-in inconsistency which could render its use in synthesis planning questionable. Decalin is used as an illustrative example of the use and implications of our results.

28 October 2004
Verified
Book Chapter
Open access
LALars Arge
Lars Arge
GBGerth Stølting Brodal
Gerth Stølting Brodal
RFRolf Fagerberg
Rolf Fagerberg

26 September 2013 in Biology
Verified
Journal Article
Open access
PDF file
ASAndreas Sand
Andreas Sand
MHMorten K. Holt
Morten K. Holt
JJJens Johansen
Jens Johansen
RFRolf Fagerberg
Rolf Fagerberg
GBGerth Stølting Brodal
Gerth Stølting Brodal
TMThomas Mailund
Thomas Mailund
Distance measures between trees are useful for comparing trees in a systematic manner, and several different distance measures have been proposed. The triplet and quartet distances, for rooted and unrooted trees, respectively, are defined as the number of subsets of three or four leaves, respectively, where the topologies of the induced subtrees differ. These distances can trivially be computed by explicitly enumerating all sets of three or four leaves and testing if the topologies are different, but this leads to time complexities at least of the order n3 or n4 just for enumerating the sets. The different topologies can be counte dimplicitly, however, and in this paper, we review a series of algorithmic improvements that have been used during the last decade to develop more efficient algorithms by exploiting two different strategies for this; one based on dynamic programming and another based oncoloring leaves in one tree and updating a hierarchical decomposition of the other.