Outputs (44)

On the approximation complexity hierarchy. (2011)
Presentation / Conference Contribution
Bordewich, M. (2010, September). On the approximation complexity hierarchy. Presented at 8th International Workshop on International Workshop on Approximation and Online Algorithms, WAOA 2010, Liverpool

This paper presents an extension of Ladner’s Theorem to the approximation complexity hierarchy. In 1975 Ladner proved that if P≠NP, then there exists an incomplete problem A which is neither in P nor NP-complete. Here we show that if RP≠NP, then ther... Read More about On the approximation complexity hierarchy..

Rapid Mixing of Subset Glauber Dynamics on Graphs of Bounded Tree-Width (2011)
Book Chapter
Bordewich, M., & Kang, R. (2011). Rapid Mixing of Subset Glauber Dynamics on Graphs of Bounded Tree-Width. In L. Aceto, M. Henzinger, & J. Sgall (Eds.), Automata, languages and programming (533-544). Springer Verlag. https://doi.org/10.1007/978-3-642-22006-7_45

Motivated by the ‘subgraphs world’ view of the ferromagnetic Ising model, we develop a general approach to studying mixing times of Glauber dynamics based on subset expansion expressions for a class of graph polynomials. With a canonical paths argume... Read More about Rapid Mixing of Subset Glauber Dynamics on Graphs of Bounded Tree-Width.

Accuracy Guarantees for Phylogeny Reconstruction Algorithms Based on Balanced Minimum Evolution. (2010)
Presentation / Conference Contribution
Bordewich, M., & Mihaescu, R. (2010, September). Accuracy Guarantees for Phylogeny Reconstruction Algorithms Based on Balanced Minimum Evolution. Presented at 10th Workshop on Algorithms in Bioinformatics (WABI 2010), Liverpool

Distance based phylogenetic methods attempt to reconstruct an accurate phylogenetic tree relating a given set of taxa from an estimated matrix of pair-wise distances between taxa. This paper examines two distance based algorithms (GreedyBME and FastM... Read More about Accuracy Guarantees for Phylogeny Reconstruction Algorithms Based on Balanced Minimum Evolution..

A Network Approach to Study Karyotypic Evolution: The Chromosomal Races of the Common Shrew (Sorex araneus) and House Mouse (Mus musculus) as Model Systems (2010)
Journal Article
White, T. A., Bordewich, M., & Searle, J. 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. https://doi.org/10.1093/sysbio/syq004

The development of methods to reconstruct phylogenies from karyotypic data has lagged behind what has been achieved with molecular and morphological characters. This hampers our understanding of the role of chromosomal rearrangements in speciation, w... Read More about A Network Approach to Study Karyotypic Evolution: The Chromosomal Races of the Common Shrew (Sorex araneus) and House Mouse (Mus musculus) as Model Systems.

Optimizing phylogenetic diversity across two trees (2009)
Journal Article
Bordewich, M., Semple, C., & Spillner, A. (2009). Optimizing phylogenetic diversity across two trees. Applied Mathematics Letters, 22(5), 638-641. https://doi.org/10.1016/j.aml.2008.05.004

We present a polynomial-time algorithm for finding an optimal set of taxa that maximizes the weighted sum of the phylogenetic diversity across two phylogenetic trees. This resolves one of the challenges proposed as part of the Phylogenetics Programme... Read More about Optimizing phylogenetic diversity across two trees.

Consistency of Topological Moves Based on the Balanced Minimum Evolution Principle of Phylogenetic Inference (2009)
Journal Article
Bordewich, M., Gascuel, O., Huber, K., & Moulton, V. (2009). Consistency of Topological Moves Based on the Balanced Minimum Evolution Principle of Phylogenetic Inference. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 6(1), 110-117. https://doi.org/10.1109/tcbb.2008.37

Many phylogenetic algorithms search the space of possible trees using topological rearrangements and some optimality criterion. FastME is such an approach that uses the balanced minimum evolution (BME) principle, which computer studies have demonstra... Read More about Consistency of Topological Moves Based on the Balanced Minimum Evolution Principle of Phylogenetic Inference.

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.