Steven Kelk's homepage
I am an Associate Professor at the Department
of Data Science and Knowledge
Engineering (DKE) at Maastricht University in the Netherlands, where I
am the area coordinator of the Algorithms,
Complexity and Optimization
(ALGOPT) group. My
contact details are here. I was
vicechair of the Maastricht
Young Academy (MYA) from 20172019.
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 graph theory, phylogenetics, fixed parameter tractability,
approximation algorithms and (more generally) combinatorial
optimization
within computational biology. Here is a short
video about my research.
Outside university I am active on issues relating to
public services and social justice, particularly housing and education, and I am a
board member of Housing Association
Soweto.
Maastricht students: I am also available for bachelor and masters
projects, see these slides for my preferred
generic research
topics. More detailed topics will be announced each year via the
Bachelor/Master thesis coordinators.
Publications/Papers
(see also my
Google
Scholar and
DBLP
pages  note that DBLP only indexes my computer science publications,
some bio(informatics) and math publications are missing.)
 Convex characters,
algorithms and matchings, Steven Kelk,
Ruben Meuwese and Stephan Wagner, submitted late November
2021.
 Sharp upper and lower
bounds on a restricted class of convex
characters, Steven Kelk and Ruben Meuwese, submitted 22nd July
2021.
 Applicability of several rooted phylogenetic network algorithms for
representing the evolutionary history of SARSCoV2, Rosanne Wallin, Leo
van Iersel, Steven Kelk and Leen Stougie, to appear in BMC Biology
and Evolution, link
 An improved kernel for the flip distance problem on simple convex
polygons, Miguel Bosch Calvo and Steven Kelk, May 2021. Accepted to
appear at
the Canadian Conference
on Computational Geometry 2021. Proceedings are here.
 A modified Integer Linear Programming formulation for the construction
of classification trees, Van Dijk et al, unpublished manuscript, march
2021.
 Reflections on kernelizing
and computing unrooted agreement forests.
Rim van Wersch, Steven Kelk, Simone Linz and Georgios Stamoulis, 14th
December 2020. To appear in Annals of
Operations Research. There is some supporting data/code here,
including the lowerboundsviasampling code. A copy of Tubro is available on request.
 This blog
posting by Rosanne Wallin, Leo van Iersel, Mark Jones,
myself and Leen Stougie summarizes the MSc work of Roseanne Wallin,
in which she constructs rooted phylogenetic networks for SARSCoV2.
November 16th
2020.
 Short opinion piece: "Phylogenetics
and parameterized complexity" in
the October 2020 edition of the Parameterized Complexity newsletter.
 In July 2020 I was awarded an NWO KLEIN 1 grant for 1 PhD student to
work on kernelization in phylogenetics. Formal recruitment has begun,
please apply here.
Informal queries from
(serious) candidates are welcome. The main goal of the project is
to extend the work in the 'New reduction rules for the tree bisection and
reconnection distance' article, below. Update 22nd December:
The position has now been filled.
 New FPT algorithms for
finding the temporal hybridization number for
sets of phylogenetic trees, Sander Borst, Leo van Iersel, Mark Jones,
Steven Kelk, July 2020
 New reduction rules for the
tree bisection and reconnection distance,
Steven Kelk and Simone Linz, Annals of Combinatorics (2020), DOI
 Maximum parsimony distance
on phylogenetic trees: a linear kernel and
constant factor approximation algorithm. Mark Jones, Steven Kelk and
Leen Stougie, arXiv version april 2020, to appear in Journal of Computer
and System Sciences.
 Cutting an alignment with
Ockham's razor. Mark Jones, Philippe
Gambette, Leo van Iersel, Remie Janssen, Steven Kelk, Fabio Pardi
and Celine Scornavacca. Submitted, October 2019.
 The accompanying software CUTAL is available here.
 Treewidth of display
graphs: bounds, brambles and applications,
Remie Janssen, Mark Jones, Steven Kelk, Georgios Stamoulis, Taoyang Wu.
Journal of Graph Algorithms and Applications 23(4): 715743 (2019)
 A tight kernel for
computing the tree bisection and
reconnection distance between two phylogenetic trees, Steven Kelk and
Simone Linz. SIAM Journal on Discrete Mathematics, 2019, Vol. 33, No. 3
: pp. 15561574. There is a blog
posting about this article.
 A machine learning
approach to algorithm selection
for exact computation of treewidth. Borislav Slavchev, Evelina
Masliankova, Steven Kelk, accepted september 2019. Algorithms 2019,
12(20), 200. (Part of the special issue on New Frontiers in Parameterized
Complexity and
Algorithms).
 Deciding the existence of a
cherrypicking sequence is hard
on two trees, Janosch Docker, Leo van Iersel, Steven Kelk and Simone
Linz, to appear in Discrete Applied Mathematics (accepted January
2019, submitted 30th November 2017.)
 A third strike against
perfect phylogeny, Leo van Iersel, Mark Jones
and Steven Kelk, arXiv preprint 19th april 2018. To appear in Systematic
Biology.

Integrality gaps for colorful matchings
, Steven
Kelk and Georgios Stamoulis, to appear in Discrete Optimization,
december 2018 (link).
 Finding
a most
parsimonious or likely tree in a network with respect to
an alignment. Steven Kelk, Fabio Pardi, Céline Scornavacca, Leo van
Iersel, to appear in Journal of Mathematical
Biology (2018).
 Discovery of important subsequences in
electrocardiogram beats using the nearest
neighbour algorithm , Ricards Marcinkevics, Steven Kelk, Carlo Galuzzi
and Berthold Stegemann, January 2019. (Interested in publishing this
paper? Please contact Ricards or myself).
 Treewidth distance on
phylogenetic trees. Steven Kelk, Georgios
Stamoulis, Taoyang Wu, to appear in Theoretical Computer Science
(2018), link,
preprint: CoRR abs/1703.10840 (2017)
 On
a fixed haplotype variant of the minimum
error correction problem, Axel Goblet, Steven Kelk, Matus
Mihalak and Georgios Stamoulis, submitted 9th march 2018.
Proceedings of COCOON 2018.
 New!
ERC Consolidator grant awarded to Dr. Cameron Browne, who will
join our department in mid2018. His research, about (the history of)
board games, will be embedded in both our Game AI and phylogenetics research groups.
For full story see here.
 New Lorentz workshop confirmed for Summer 2018! Distinguishability
in
genealogical phylogenetic networks, 1317 August 2018, Lorentz Center,
Leiden. Scientific organizers: Leo van Iersel, Steven Kelk, David Morrison
and Celine Scornavacca. Details follow soon.
 Improving
Card Fraud Detection Through Suspicious Pattern Discovery. Fabian Braun, Olivier Caelen, Evgueni N. Smirnov, Steven Kelk,
Bertrand Lebichot. IEA/AIE (2) 2017: 181190
 On unrooted and
rootuncertain variants of
several wellknown phylogenetic network problems, Leo van Iersel,
Steven
Kelk, Georgios Stamoulis, Leen Stougie and Olivier Boes, 2nd September
2016, to appear in Algorithmica (2017)
 ToTo:
An open database for computation, storage and retrieval of tree
decompositions, Rim van Wersch and Steven Kelk, august 2016,
Discrete Applied Mathematics 217P3 (2017)
pp. 389393. A preprint is available here.
 A note on convex characters,
Fibonacci numbers and exponentialtime algorithms, Steven Kelk and
Georgios Stamoulis, 27th July 2016. (An earlier version of this article
was released in August 2015) Advances in Applied
Mathematics, Volume 84, March 2017, Pages 3446. (DOI)
 The accompanying software CONVEXMPDIST is available here and the software CONVEXCOUNT
is available here.
 Book
review of "GenomeScale Algorithm Design:
Biological Sequence Analysis in the Era of HighThroughput Sequencing" by
Makinen et al, SIGACT News 47(3):1518 (2016).
 Do branch lengths help to
locate a tree in a phylogenetic network?
Philippe Gambette, Leo van Iersel, Steven Kelk, Fabio Pardi, Celine
Scornavacca. Bulletin of Mathematical Biology 78(9), 17731795 (2016).
 Book review of
"ReCombinatorics: The Algorithmics of Ancestral Recombination Graphs and
Explicit Phylogenetic Networks" by Dan Gusfield.
SIGACT News 47(1), 1215, March 2016. (The preedit of the
review can be read here.)
 Reduction rules for the
maximum parsimony distance on phylogenetic
trees, Steven Kelk, Mareike Fischer, Vincent Moulton, Taoyang Wu.
Theoretical Computer Science (2016),
DOI.
 A resolution of the static formulation question for the problem of
computing the history bound, Julia Matsieva, Steven Kelk, Celine
Scornavacca, Chris Whidden, and Dan Gusfield, to appear in
IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB) 2016.
 From phylogenetic trees
to phylogenetic networks: possible applications outside biology 
talk I gave at the
Lorentz workshop Capturing
phylogenetic algorithms for linguistics (Leiden, October 26th30th
2015).
 A linear bound on the number
of states in optimal
convex characters for maximum parsimony distance, Olivier Boes,
Mareike
Fischer, Steven Kelk, 21st June 2015. To appear in
IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB) 2016.
 Phylogenetic
incongruence through the lens of Monadic Second Order
logic, Steven Kelk, Leo van Iersel, Celine Scornavacca, Mathias
Weller, Journal of Graph Algorithms and Applications (JGAA) 20(2), pp. 189215 (2016). Note that
the arXiv version is somewhat different
to the JGAA version.
 On the complexity of
computing MP
distance between binary phylogenetic trees, Steven Kelk and Mareike
Fischer (December 12th 2014). Annals of Combinatorics 21(4), 573604,
2017.
 Accompanying software MPDIST is here.
 Satisfying ternary
permutation constraints by multiple linear orders
or phylogenetic trees, Leo van Iersel, Steven Kelk, Nela Lekic and
Simone Linz (October 9th 2014). To appear in Theoretical Computer
Science (2015), DOI
 The agreement problem for
unrooted phylogenetic trees is FPT,
Celine Scornavacca, Leo van Iersel, Steven Kelk, and David Bryant (June 2014),
to appear in Journal of Graph Algorithms and Applications (JGAA).
 On the challenge of
reconstructing level1 phylogenetic
networks from
triplets and clusters, Philippe Gambette, Katharina Huber, Steven
Kelk,
to appear in Journal of Mathematical Biology (2016/2017).
 On low treewidth graphs and
supertrees, Alexander Grigoriev, Steven
Kelk and Nela Lekic, 11th february 2014. Preliminary version in
AlCoB 2014. Journal version
to appear in Journal of Graph Algorithms and Applications (JGAA), June 2015.

Hybridization Number on Three Rooted Binary Trees is EPT.
Leo van Iersel, Steven Kelk, Nela
Lekic, Chris Whidden and Norbert Zeh. To appear in SIAM
Journal on Discrete Mathematics (SIDMA) 2016. (Earlier
title was Hybridization Number on Three Trees).
 On the Maximum Parsimony
distance between phylogenetic trees,
Mareike Fischer and Steven Kelk, Annals of Combinatorics 20(1), pp 87113 (2016).

A short note on exponentialtime
algorithms for hybridization number, Leo van Iersel, Steven Kelk, Nela Lekic, Leen Stougie, 4
december 2013.
 A practical
approximation algorithm for solving
massive instances of hybridization number for
binary and nonbinary trees, Leo van Iersel, Nela Lekic, Steven
Kelk, Celine
Scornavacca, November 2013, BMC Bioinformatics (2014).
 This is the journal version of the WABI 2012 paper. We have
extended it to nonbinary trees.
 Kernelizations for the
hybridization number problem on multiple nonbinary trees, Leo van
Iersel and Steven Kelk, 16th November 2013. To appear in Journal of
Computer and System Sciences (JCSS), 2016. Conference version
in WG
2014. See also the TREEDUCE software below.
 Fighting network space: it is
time for an SQLtype language to filter
phylogenetic networks, Steven Kelk, Simone Linz, and David A.
Morrison,
October 2013 (unpublished opinion piece, arXiv).
 Exact reconciliation of
undated trees. Leo van Iersel, Celine
Scornavacca and Steven Kelk, september 2013 (arXiv manuscript).

See the accompanying software ILPEACE.
 Ancient
dispersal of the human fungal pathogen Cryptococcus gattii
from the Amazon rainforest, Hagen et. al., PLOS ONE, June 2013. (Link
to press
release).
 Recent advances in rooted phylogenetic networks: the
long road to explicit hypothesis generation. Talk
at conference Mathematical and Computational Evolutionary Biology (MCEB
2013),
May 2013.
 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
Scornavacca,
arxiv (11 feb 2013). To appear in SIDMA (2015).
 See also the accompanying software MPNet.
 Approximation algorithms for
nonbinary agreement forests, to appear in SIDMA (2014). This extends
the article 'Computing nonbinary agreement forests' by including results for MAAF (and not just MAF).
 Computing nonbinary agreement
forests,
Leo van Iersel, Steven Kelk, Nela Lekic and Leen Stougie, arXiv (2012)
 See also the MAF
software on Leo's webpage.
 What
mathematical optimization can, and cannot do, for biologists 
presentation at the Lorentz workshop on the Future of Phylogenetic
Networks (October 2012).
 Optimal
flux spaces of genomescale stoichiometric models are
determined by a few subnetworks, Steven Kelk, Brett Olivier, Leen
Stougie,
Frank Bruggeman, Nature Scientific Reports 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. Update 9th September 2013: I
have just released Version 2 of TerminusEst, which is much faster
than the original version when hashing is switched on.
 A practical approximation
algorithm for solving
massive instances of hybridization number, Leo van Iersel, Steven
Kelk,
Nela Lekic and Celine Scornavacca, may 2012. To appear in WABI 2012. The
program
CycleKiller can be downloaded here.
 Cycle killer...qu'estce 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. To appear in SIAM
Journal on Discrete Mathematics (SIDMA).
 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. To appear in Algorithmica, link.
 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, IEEE/ACM Transactions on Computational
Biology and Bioinformatics (TCBB) 9(2) (MarchApril 2012), pp. 517534.
 When two trees
go to war, Leo van Iersel and Steven Kelk,
Journal of Theoretical Biology 269 (2011), pp. 245255.
 A short note on the tractability of constructing phylogenetic networks from clusters,
Leo van Iersel and Steven Kelk, arXiv preprint 22 december 2009.
 A Practical Algorithm for Reconstructing Level1 Phylogenetic
Networks, Katharina T. Huber, Leo van Iersel, Steven Kelk, Radoslaw
Suchecki, IEEE/ACM Transactions on Computational Biology and
Bioinformatics (TCBB) 8(3) (MayJune 2011), pp. 635649.
 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 preprint 16 october 2009. March 2010: Accepted to ISMB2010, thereafter to
appear in Bioinformatics 2010
26(12):i124i131.
 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,
IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB)
8(5) (SeptOct 2011) pp. 13581372.
 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.
207235 (2011). (Available online)
 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 levelk phylogenetic networks,
Leo van Iersel, Steven Kelk, Matthias Mnich,
Journal of Bioinformatics and Computational Biology (JBCB) 7(4):597623 (2009)
 Worstcase optimal approximation algorithms for maximizing
triplet consistency within phylogenetic networks, Jaroslaw Byrka,
Pawel Gawrychowski, Katharina T. Huber, Journal of Discrete Algorithms 8(1):6575 (2010)
 Constructing level2
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):667681 (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 AprilJune 2008 (Vol. 5, No. 2)
pp. 301312. 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. 592611 (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. 1336 (2007), DOI
10.1007/s004530070029z
 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 36, 2005, LNCS 3692 / 2005, pp. 128139.
 On the relative complexity of
approximately counting Hcolourings, Steven Kelk, PhD Thesis, University of Warwick, 2004.
(3.5mb,
PDF)
 The
complexity of choosing an Hcolouring (nearly) uniformly at random, L.A. Goldberg, S.
Kelk and M. Paterson, SICOMP, 33(2) 416432 (2004) copyright SIAM (preliminary version
STOC 2002)
Links to pages of some regular coauthors
Links to books (etc.) about phylogenetic networks
Software for phylogenetic networks (and trees)  and related
topics
 ConvexBound
 generates via sampling strong lower bounds on dMP and dTBR.
 CUTAL
 optimally partitions an alignment into blocks,
using parsimony as the guiding principle. (Main developer is Mark
Jones).
 CONVEXCOUNT 
counts or samples convex characters on a given unrooted binary tree
 CONVEXMPDIST
(does not use ILP)  computes maximum parsimony distance exactly
 MPDIST (uses
ILP)  computes maximum parsimony distance exactly
 TREEDUCE
 kernelizes arbitrary sets of rooted nonbinary trees in polynomial
time
 Nonbinary
CycleKiller  approximates hybridization number on two nonbinary
rooted trees by optimally
breaking cycles in an induced graph
 ILPEACE 
computes optimal reconciliation of two trees, using ILP
 MPNet 
computes parsimony score of a phylogenetic network, uses ILP
 MAF  computes
maximum agreement forest on nonbinary trees
 TerminusEst 
FPT algorithm that computes hybridization number exactly on two rooted
nonbinary trees. Much faster than you would expect :)
 CycleKiller 
approximates hybridization number on two binary rooted trees by
optimally inducing cycles in an induced graph
 CASS 
computes a phylogenetic network of low level (i.e. few reticulations per
biconnected component) from a set of softwired clusters
 LEV1ATHAN  computes a level1 network
that displays as many of the given input triplets as possible
 SIMPLISTIC  constructs levelk
networks from dense sets of input triplets
 MARLON  constructs level1 networks
with a minimum number of reticulations, from a dense set of input
triplets
 LEVEL2  constructs a level2
network consistent with a given set of input triplets
Miscellaneous scientific links
Miscellaneous publications
Miscellaneous political links
Random stuff
 Rush Hour by
Jane Wiedlin  possibly the best pop song ever?
 My favourite band: VNV
Nation (no, they don't sound like Jane
Wiedlin). Other bands I like very much: Depeche Mode, New Order, REM,
Idlewild, Lord Huron.
 Favourite album: Stone Roses (by the Stone Roses). There are so
many amazing
songs on this album.
 I'm a huge fan of Cricket and also enjoy
playing it when the opportunity arises (I guess I would describe myself
as a mediumpace rightarm seam bowler who gets up to mediumfast if I'm
not too stiff...) If you have no idea what Cricket is, the description
of the game on Wikipedia
is long but comprehensive. This five
minute video does a pretty good of
explaining the basic rules. I had the pleasure of being at Headingley
on Day 4 of the third Ashes test, August 25th
2019...short highlights are here. A day to never
forget.
Last updated: 25th November 2021.