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 projects.

Publications/Papers

(See also the website of my co-author Leo van Iersel.)

Cycle killer...qu'est-ce que c'est? On the comparative approximability of hybridization number and directed feedback vertex set, Steven Kelk, Leo van Iersel, Nela Lekic, Simone Linz, Celine Scornavacca, Leen Stougie, december 22nd 2011.
A note on efficient computation of hybridization number via softwired clusters, Steven Kelk, august 2011.
Constructing minimal phylogenetic networks from softwired clusters is fixed parameter tractable, Steven Kelk and Celine Scornavacca, august 2011, submitted.
Book review: Phylogenetic Networks: Concepts, Algorithms and Applications, Steven Kelk, Systematic Biology 2011; doi: 10.1093/sysbio/syr054
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, march 2011, to appear in IEEE/ACM Transactions on Computational Biology and Bioinformatics.
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, arXiv pre-print 21 october 2009. To appear in IEEE/ACM Transactions on Computational Biology and Bioinformatics.
- LEV1ATHAN, the algorithm from the above paper, is available for download from this website.
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 26(12):i124-i131.
- CASS, the algorithm from the above paper, has now been incorporated into Dendroscope. CASS also has its own website, see here.
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, arXiv pre-print 8 september 2009, updated 26 july 2010. To appear in IEEE/ACM Transactions on Computational Biology and Bioinformatics.
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, june 2009: to appear in Algorithmica (available on-line)
- MARLON (Minimum Amount of Reticulation Level One Network) can be downloaded here.
- A version of the paper has been accepted to appear in ISAAC2008.
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)

In February 2008 we produced a new version of the paper, with a heavily optimized running time for the derandomization, and a very fast triplet consistency checking algorithm as subroutine.
Slides from a presentation about this article, given at both Technische Universiteit Eindhoven and the Isaac Newton Institute (Cambridge, England).

Constructing level-2 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).
- Powerpoint slides used in presentations at University of East Anglia and University of Liverpool, summer 2007.
- September 2007: Here is a practical implementation of the algorithm in Java: LEVEL2
- December 2007: The article has been accepted to appear in RECOMB2008.
Shorelines of islands of tractability: Algorithms 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).
- There is a poster here about this paper.
- Conference version appears in Algebraic Biology 2007, LNCS4545 pp. 292--307, DOI 10.1007/978-3-540-73433-8_21
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 10.1007/s00453-007-0029-z
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. (3.5mb, PDF)
The 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 STOC 2002)

Software for phylogenetic networks

Miscellaneous publications

A (very) rough guide to Amsterdam housing policy, Carla Huisman and Steven Kelk, 2008. As its name suggests, it's very rough...
Trading It Away - How GATS Threatens UK Higher Education, Steven Kelk and Jess Worth, October 2002. This report disappeared from the internet several years ago and after much searching I succeeded in finding and uploading a PDF version of it.

Miscellaneous links

Last updated: 22nd December, 2011.