Outputs (4)

Selecting Taxa to Save or Sequence: Desirable Criteria and a Greedy Solution (2008)
Journal Article
Bordewich, M., Rodrigo, A., & Semple, C. (2008). Selecting Taxa to Save or Sequence: Desirable Criteria and a Greedy Solution. Systematic Biology, 57(6), 825-834. https://doi.org/10.1080/10635150802552831

Three desirable properties for any method of selecting a subset of evolutionary units (EUs) for conservation or for genomic sequencing are discussed. These properties are spread, stability, and applicability. We are motivated by a practical case in w... Read More about Selecting Taxa to Save or Sequence: Desirable Criteria and a Greedy Solution.

A 3-approximation algorithm for the subtree distance between phylogenies (2008)
Journal Article
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. https://doi.org/10.1016/j.jda.2007.10.002

In this paper, we give a (polynomial-time) 3-approximation algorithm for the rooted subtree prune and regraft distance between two phylogenetic trees. This problem is known to be NP-complete and the best previously known approximation algorithm is a... Read More about A 3-approximation algorithm for the subtree distance between phylogenies.

Path Coupling Using Stopping Times and Counting Independent Sets and Colourings in Hypergraphs (2008)
Journal Article
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. https://doi.org/10.1002/rsa.20204

We analyse the mixing time of Markov chains using path coupling with stopping times. We apply this approach to two hypergraph problems. We show that the Glauber dynamics for independent sets in a hypergraph mixes rapidly as long as the maximum degree... Read More about Path Coupling Using Stopping Times and Counting Independent Sets and Colourings in Hypergraphs.

Nature Reserve Selection Problem: A Tight Approximation Algorithm (2008)
Journal Article
Bordewich, M., & Semple, C. (2008). Nature Reserve Selection Problem: A Tight Approximation Algorithm. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 5(2), 275-280. https://doi.org/10.1109/tcbb.2007.70252

The nature reserve selection problem is a problem that arises in the context of studying biodiversity conservation. Subject to budgetary constraints, the problem is to select a set of regions to be conserved so that the phylogenetic diversity of the... Read More about Nature Reserve Selection Problem: A Tight Approximation Algorithm.