physical-isolation-endospores-from-environmental-samples-targeted

Physical Isolation of Endospores from Environmental Samples by Targeted Lysis of Vegetative Cells

Endospore formation is a survival strategy found among some bacteria from the phylum Firmicutes. During endospore formation, these bacteria enter a ...

University of Neuchatel

We propose new algorithms for computing pairwise rearrangement scenarios that conserve the combinatorial structure of genomes. More precisely, we investigate the problem of sorting signed permutations by reversals without breaking common intervals. We describe a combinatorial framework for this problem that allows us to characterize classes of signed permutations for which one can compute, in polynomial time, a shortest reversal scenario that conserves all common intervals. In particular, we define a class of permutations for which this computation can be done in linear time with a very simple algorithm that does not rely on the classical Hannenhalli-Pevzner theory for sorting by reversals. We apply these methods to the computation of rearrangement scenarios between permutations obtained from 16 synteny blocks of the X chromosomes of the human, mouse, and rat.

Perfect sorting by reversals is not always difficult.

Developing methods for computing phylogenetic networks from biological data is an important problem posed by molecular evolution and much work is currently being undertaken in this area. Although promising approaches exist, there are no tools available that biologists could easily and routinely use to compute rooted phylogenetic networks on real datasets containing tens or hundreds of taxa. Biologists are interested in clades, i.e. groups of monophyletic taxa, and these are usually represented by clusters in a rooted phylogenetic tree. The problem of computing an optimal rooted phylogenetic network from a set of clusters, is hard, in general. Indeed, even the problem of just determining whether a given network contains a given cluster is hard. Hence, some researchers have focused on topologically restricted classes of networks, such as galled trees and level-k networks, that are more tractable, but have the practical draw-back that a given set of clusters will usually not possess such a representation.

Computing galled networks from real data.

We study the problem of transforming a multichromosomal genome into another using Double Cut-and-Join (DCJ) operations, which simulates several types of rearrangements, as reversals, translocations, and block-interchanges. We introduce the notion of a DCJ scenario that does not break families of common intervals (groups of genes co-localized in both genomes). Such scenarios are called perfect, and their properties are well known when the only considered rearrangements are reversals. We show that computing the minimum perfect DCJ rearrangement scenario is NP-hard, and describe an exact algorithm which exponential running time is bounded in terms of a specific pattern used in the NP-completeness proof. The study of perfect DCJ rearrangement leads to some surprising properties. The DCJ model has often yielded algorithmic problems which complexities are comparable to the reversal-only model. In the perfect rearrangement framework, however, while perfect sorting by reversals is NP-hard if the family of common intervals to be preserved is nested, we show that finding a shortest perfect DCJ scenario can be answered in polynomial time in this case. Conversely, while perfect sorting by reversals is tractable when the family of common intervals is weakly separable, we show that the corresponding problem is still NP-hard in the DCJ case. This shows that despite the similarity of the two operations, easy patterns for reversals are hard ones for DCJ, and vice versa.

Computation of perfect DCJ rearrangement scenarios with linear and circular chromosomes.

Phylogenetic networks were introduced to describe evolution in the presence of exchanges of genetic material between coexisting species or individuals. Split networks in particular were introduced as a special kind of abstract network to visualize conflicts between phylogenetic trees which may correspond to such exchanges. More recently, methods were designed to reconstruct explicit phylogenetic networks (whose vertices can be interpreted as biological events) from triplet data. In this article, we link abstract and explicit networks through their combinatorial properties, by introducing the unrooted analog of level-k networks. In particular, we give an equivalence theorem between circular split systems and unrooted level-1 networks. We also show how to adapt to quartets some existing results on triplets, in order to reconstruct unrooted level-k phylogenetic networks. These results give an interesting perspective on the combinatorics of phylogenetic networks and also raise algorithmic and combinatorial questions.

Quartets and unrooted phylogenetic networks.

The Saprolegnia-Achlya clade comprises species of major environmental and economic importance due to their negative impact on aquaculture and aquatic ecosystems by threatening fishes, amphibians, and crustaceans. However, their taxonomy and phylogenetic relationships remain unresolved and suffer from many inconsistencies, which is a major obstacle to the widespread application of molecular barcoding to identify pathogenic strains with quarantine implications. We assessed phylogenetic relationships of major genera using three commonly used markers (ITS, SSU rRNA, and LSU rRNA). A consensus tree of the three genes provided support for nine clades encompassing eleven documented genera and a new clade (SAP1) that has not been described morphologically. In the course of this study, we isolated a new species, Newbya dichotoma sp. nov., which provided the only culture available for this genus. In parallel, we attempted to summarize the evolution of traits in the different genera, but their successive reversals rendered the inference of ancestral states impossible. This highlights even more the importance of a bar-coding strategy for saprolegniacean parasite detection and monitoring.

Multiple barcode assessment within the Saprolegnia-Achlya clade (Saprolegniales, Oomycota, Straminipila) brings order in a neglected group of pathogens.

Article	Year
Perfect sorting by reversals is not always difficult. IEEE/ACM transactions on computational biology and bioinformatics / IEEE, ACM\| PubMed ID: 17277409	2007
Computing galled networks from real data. Bioinformatics (Oxford, England)\| PubMed ID: 19478021	2009
Computation of perfect DCJ rearrangement scenarios with linear and circular chromosomes. Journal of computational biology : a journal of computational molecular cell biology\| PubMed ID: 19803733	2009
Quartets and unrooted phylogenetic networks. Journal of bioinformatics and computational biology\| PubMed ID: 22809417	2012
Multiple barcode assessment within the Saprolegnia-Achlya clade (Saprolegniales, Oomycota, Straminipila) brings order in a neglected group of pathogens. IMA fungus\| PubMed ID: 25734033	2014

Christophe Paul

Biography

JoVE Journal Publications

Other Publications