Profile

Dr Magnus Bordewich, MMath DPhil PGCAP

Personal web page

(email at m.j.r.bordewich@durham.ac.uk)

Biography

I have been a lecturer in Computer Science at Durham University since January 2006. Prior to this I held posts as a post-doctoral fellow at the School of Computing, Leeds University and at the Department of Mathematics and Statistics at the University of Canterbury, New Zealand. My D.Phil. and undergraduate degree (MMath) were conducted at the Department of Mathematics, Oxford University.

Indicators of Esteem

• 2010: 'Top cited article' award: I was awarded a “Top Cited Article 2005-2010” award from the journal Discrete Applied Mathematics, awarded by Elsevier in September 2010. Our article "Computing the minimum number of hybridization events for a consistent evolutionary history" is the 3rd most cited article published in the period 2005-2010, from a total of over 1000 (approx 270 per year), having already obtained over 65 citations listed on Google scholar.

Research Groups

School of Engineering and Computing Sciences

• Algorithms and Complexity Research Group

Department of Computer Science

• Algorithms and Complexity

Research Interests

• Discrete mathematics, theoretical computer science and applications in phylogenetics.

Selected Publications

Edited works: conference proceedings

• Bordewich, Magnus & Mihaescu, Radu (2010). Accuracy Guarantees for Phylogeny Reconstruction Algorithms Based on Balanced Minimum Evolution. 10th Workshop on Algorithms in Bioinformatics (WABI 2010), Liverpool, Springer.
• Bordewich, Magnus (2010). On the approximation complexity hierarchy. 8th Workshop on Approximation and Online Algorithms (WAOA 2010), Liverpool, Springer.
• Bordewich, M., Dyer, M. & Karpinski, M. (2006). Stopping times, metrics and approximate counting. 33rd International Colloquium of Automata, Languages and Programming (ICALP 2006), Venice, Italy, Springer.
• Bordewich, M., Dyer, M. & Karpinski, M. (2005). Path coupling using stopping times. 15th International Symposium Fundamentals of Computation Theory FCT 2005, Lubeck, Germany, Springer.

Journal papers: academic

• Bordewich, M. & Semple, C. (2012). Budgeted Nature Reserve Selection with diversity feature loss and arbitrary split systems. Journal of Mathematical Biology 64(1-2): 69-85.
• White, Thomas A., Bordewich, Magnus & Searle, Jeremy B. (2010). A Network Approach to Study Karyotypic Evolution: The Chromosomal Races of the Common Shrew (Sorex araneus) and House Mouse (Mus musculus) as Model Systems. Systematic Biology 59(3): 262-276.
• Bordewich, M., Gascuel, O., Huber, K. T. & Moulton, V. (2009). Consistency of Topological Moves Based on the Balanced Minimum Evolution Principle of Phylogenetic Inference. Transactions on Computational Biology and Bioinformatics 6(1): 110-117.
• Bordewich, M., Semple, C. & Spillner, A. (2009). Optimizing phylogenetic diversity across two trees. Applied Mathematics Letters 22(5): 638-641.
• Bordewich, M., McCartin, C. & Semple, C. (2008). A 3-approximation algorithm for the subtree distance between phylogenies. Journal of Discrete Algorithms 6(3): 458-471.
• Bordewich, M. & Semple, C. (2008). Nature Reserve Selection Problem: A Tight Approximation Algorithm. Transactions on Computational Biology and Bioinformatics 5(2): 275-280.
• Bordewich, M., Karpinski, M. & Dyer, M. (2008). Path Coupling Using Stopping Times and Counting Independent Sets and Colourings in Hypergraphs. Random Structures and Algorithms 32(3): 375-399.
• Bordewich, M., Rodrigo, A. G. & Semple, C. (2008). Selecting Taxa to Save or Sequence: Desirable Criteria and a Greedy Solution. Systematic Biology 57(6): 825-834.
• Bordewich, M., Linz, S., St. John, K. & Semple, C. (2007). A Reduction Algorithm for Computing the Hybridization Number of Two Trees. Evolutionary Bioinformatics 3: 86-98.
• Bordewich, M. & Semple, C. (2007). Computing the hybridisation number of two phylogenetic trees is fixed parameter tractable. Transactions on Computational Biology and Bioinformatics 4(3): 458-466.
• Bordewich, M. & Semple, C. (2007). Computing the minimum number of hybridisation events for a consistent evolutionary history. Discrete Applied Mathematics 155(8): 914-928.
• Bordewich, M., Evans, G. & Semple, C. (2007). Extending the limits of supertree methods. Annals of Combinatorics
• Bordewich, M. & Dyer, M. (2007). Path Coupling without contraction. Journal of Discrete Algorithms 5(2): 280-292.
• Bordewich, M., Semple, C. & Steel, M. A. (2006). Identifying X-Trees with Few Characters. Electronic Journal of Combinatorics 13(1): R83.
• Bordewich, M., Freedman, M., Lovasz, L. & Welsh, D. (2005). Approximate counting and quantum computation. Combinatorics, probability and computing 14(5-6): 737-754.
• Bordewich, M., Huber, K. & Semple, C. (2005). Identifying phylogenetic trees. Discrete Mathematics 300(1-3): 30-43.
• Bordewich, M. & Semple, C. (2005). On the computational complexity of the rooted subtree prune and regraft distance. Annals of combinatorics 8(4): 409-423.
• Bordewich, M. (2004). Approximating the number of acyclic orientations for a class of sparse graphs. Combinatorics, probability and computing 13(1): 1-16.
• Bordewich, M., Semple, C. & Talbot, J. (2004). Counting Consistent Phylogenetic Trees is #P-complete. Advances in Applied Mathematics 33(2): 416-430.

Theses: PhD

• Bordewich, M. (2003). The Complexity of Counting and Randomised Approximation. Department of Mathematics. Oxford University, New College, Oxford University. PhD.

Show all publications

Related Links

• Full details of my publications can be found on my personal webpage.

Grants Awarded

• 2010: Approximation and mixing times in the ferromagneti (£250380.00 from Epsrc)
• 2006: RANDOMISED ALGORITHMS AND APPROXIMATION (£222248.00 from Epsrc)

Supervises

• Mr Daniel Allsop