Steven Kelk's homepage
Since February 2011 I am Assistant Professor at the Department of Knowledge
Engineering (DKE) at Maastricht University in the Netherlands, where I work within the Networks and Strategic Optimization (NSO) cluster. My
contact details are here.
Between 2004 and 2010 I was a postdoc in the Life Sciences cluster of the Centrum voor
Wiskunde en Informatica (CWI) in Amsterdam, in the subgroup Combinatorial
Problems in Biology. I obtained my PhD in late 2003 from the Algorithms and Computational
Complexity Research Group at the University of Warwick. My supervisor was
Leslie Goldberg. My main research
interests are approximation algorithms, phylogenetic networks and combinatorial optimization within computational biology.
A PhD student for the NWO project has
been appointed, thanks to all candidates for their interest.
Please note: this website was migrated from my old CWI webpage in March
2011. Not all files have yet been transferred, so if you
cannot find something (and have already tried changing the prefix of the URL to http://skelk.sdf-eu.org/) don't hesitate to get
in touch with me.
Maastricht students: I am also available for bachelor and masters
The Future of Phylogenetic Networks
15 – 19 October 2012
- Leo van Iersel (Amsterdam)
- Steven Kelk (Maastricht)
- David Morrison (Uppsala)
- Leen Stougie (Amsterdam)
(See also the website of my co-author Leo van Iersel.)
A practical approximation
algorithm for solving
massive instances of hybridization number, Leo van Iersel, Steven
Nela Lekic and Celine Scornavacca, may 2012. To appear in WABI 2012. The
CycleKiller can be downloaded here.
Cycle killer...qu'est-ce que
c'est? On the comparative
approximability of hybridization number and directed feedback vertex
Steven Kelk, Leo van Iersel, Nela Lekic, Simone Linz, Celine
Scornavacca, Leen Stougie, december 22nd 2011. To appear in SIAM
Journal on Discrete Mathematics (SIDMA).
A note on efficient
computation of hybridization number via softwired
clusters, Steven Kelk, august 2011.
phylogenetic networks from softwired
clusters is fixed parameter tractable, Steven Kelk and Celine
august 2011. To appear in Algorithmica, link.
Book review: Phylogenetic
Networks: Concepts, Algorithms and
Applications, Steven Kelk, Systematic Biology 2011; doi:
Algorithmic aspects of
phylogenetic network construction - these are slides (in PDF) from a
talk I gave in April 2011 at the IPA
Lentedagen in the Netherlands.
On the elusiveness of
clusters, Steven Kelk and Celine
Scornavacca and Leo van Iersel, IEEE/ACM Transactions on Computational
Biology and Bioinformatics (TCBB) 9(2) (March-April 2012), pp. 517-534.
When two trees
go to war, Leo van Iersel and Steven Kelk,
Journal of Theoretical Biology 269 (2011), pp. 245-255.
A short note on the tractability of constructing phylogenetic networks from clusters,
Leo van Iersel and Steven Kelk, arXiv pre-print 22 december 2009.
A Practical Algorithm for Reconstructing Level-1 Phylogenetic
Networks, Katharina T. Huber, Leo van Iersel, Steven Kelk, Radoslaw
Suchecki, IEEE/ACM Transactions on Computational Biology and
Bioinformatics (TCBB) 8(3) (May-June 2011), pp. 635-649.
- Bapteste, E., van Iersel, L. Janke, A., Kelchner, S., Kelk, S.,
McInerney, J.O., Morrison, D.A., Nakhleh, L., Steel, M., Stougie, L. and
Whitfield, J. (2013). Networks: Expanding evolutionary thinking. Trends in
Genetics (in press).
- On Computing The Maximum
Parsimony Score Of A Phylogenetic
Network, Mareike Fischer, Leo van Iersel, Steven Kelk, Celine
arxiv (11 feb 2013). Submitted.
- See also the accompanying software MPNet.
- Approximation algorithms for
nonbinary agreement forests, dec. 21, 2012 (submitted). This extends
the article 'Computing nonbinary agreement forests' by including results for MAAF (and not just MAF).
- Computing nonbinary agreement
Leo van Iersel, Steven Kelk, Nela Lekic and Leen Stougie, arXiv (2012)
- See also the MAF
software on Leo's webpage.
flux spaces of genome-scale stoichiometric models are
determined by a few subnetworks, Steven Kelk, Brett Olivier, Leen
Frank Bruggeman, Sci. Rep. 2, 580; DOI:10.1038/srep00580 (2012)
- Towards the fixed parameter
tractability of constructing minimal
phylogenetic networks from arbitrary sets of nonbinary trees,
Steven Kelk and Celine Scornavacca, 30th July 2012. Submitted.
- A simple fixed
parameter tractable algorithm for
computing the hybridization number of two (not
necessarily binary) trees, Teresa Piovesan and Steven Kelk,
July 25th 2012. To appear in IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB).
- There is an experimental implementation of this algorithm here: TERMINUSEST.
Phylogenetic Networks Do
not Need to Be Complex: Using Fewer Reticulations to Represent
Conflicting Clusters, Leo van Iersel, Steven Kelk, Regula Rupp,
Daniel Huson, arXiv pre-print 16 october 2009. March 2010: Accepted to ISMB2010, thereafter to
appear in Bioinformatics 2010
- LEV1ATHAN, the algorithm from the above paper, is available for download from this website.
Some mathematical refinements
concerning error minimization in the genetic code, Harry Buhrman,
Peter T. S. van der Gulik, Steven M. Kelk, Wouter M. Koolen, Leen Stougie,
IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB)
8(5) (Sept-Oct 2011) pp. 1358-1372.
An early release of SIMPLISTIC (SIMPLe network heurISTIC) is now
available! SIMPLISTIC is a program, written in Java, which always returns some network consistent with 100% of the
dense input triplets. See this page for code
and documentation (28 july 2008). There is a poster here about SIMPLISTIC (and MARLON.)
Constructing the Simplest Possible Phylogenetic Network from
Triplets, Leo van Iersel and Steven Kelk, Algorithmica, 60, pp.
207-235 (2011). (Available on-line)
- CASS, the algorithm from the above paper, has now been
incorporated into Dendroscope.
CASS also has its own website, see here.
Uniqueness, intractability and
exact algorithms: reflections on level-k phylogenetic networks,
Leo van Iersel, Steven Kelk, Matthias Mnich,
Journal of Bioinformatics and Computational Biology (JBCB) 7(4):597-623 (2009)
Worst-case optimal approximation algorithms for maximizing
triplet consistency within phylogenetic networks, Jaroslaw Byrka,
Pawel Gawrychowski, Katharina T. Huber, Journal of Discrete Algorithms 8(1):65-75 (2010)
phylogenetic networks from triplets,
Leo van Iersel, Judith
Keijsper, Steven Kelk, Leen Stougie, Ferry Hagen, Teun Boekhout,
IEEE/ACM Transactions on Computational Biology and Bioinformatics, 6(4):667-681 (2009).
- MARLON (Minimum Amount of Reticulation
Level One Network) can be downloaded here.
- A version of the paper has been accepted to appear in ISAAC2008.
Shorelines of islands of tractability:
for parsimony and perfect phylogeny haplotyping problems, Leo van Iersel, Judith
Keijsper, Steven Kelk and Leen Stougie, IEEE/ACM Transactions on
Computational Biology and Bioinformatics April-June 2008 (Vol. 5, No. 2)
pp. 301-312. This is the journal version of the WABI paper
Beaches... and contains new approximation
results for PH and MPPH not found in the WABI version. The essence of the approximation results
is explained in this presentation given at Bielefeld University (Germany)
in November 2006.
Beaches of islands of tractability: Algorithms for parsimony
and minimum perfect phylogeny haplotyping problems, Leo van Iersel, Judith Keijsper,
Steven Kelk and Leen Stougie. A conference version was presented at
WABI2006. (WABI slides are available here.)
Prefix reversals on binary and ternary strings,
Cor Hurkens, Leo van Iersel, Judith Keijsper, Steven Kelk, Leen Stougie, John Tromp,
SIAM Journal on Discrete Mathematics, 21(3), pp. 592--611 (2007).
On the complexity of the Single Individual SNP Haplotyping
Problem, Rudi Cilibrasi, Leo van Iersel, Steven Kelk and John Tromp,
Algorithmica 49(1), pp. 13-36 (2007), DOI
On the complexity of several haplotyping problems, Rudi
Cilibrasi, Leo van
Iersel, Steven Kelk and John Tromp, Algorithms in Bioinformatics: 5th International Workshop, WABI 2005,
Mallorca, Spain, October 3-6, 2005, LNCS 3692 / 2005, pp. 128-139.
On the relative complexity of
approximately counting H-colourings, Steven Kelk, PhD Thesis, University of Warwick, 2004.
complexity of choosing an H-colouring (nearly) uniformly at random, L.A. Goldberg, S.
Kelk and M. Paterson, SICOMP, 33(2) 416-432 (2004) copyright SIAM (preliminary version
- Powerpoint slides used in
presentations at University of East Anglia and University of Liverpool,
- September 2007: Here is a practical implementation of the algorithm in Java: LEVEL2
- December 2007: The article has been accepted to appear in RECOMB2008.
Links to books (etc.) about phylogenetic networks
Software for phylogenetic networks
Last updated: 23rd May, 2013.