Browsing by Subject "ENUMERATION"

Sort by: Order: Results:

Now showing items 1-3 of 3
  • Talvitie, Topi; Koivisto, Mikko (AAAI Press, 2019)
    Exploring directed acyclic graphs (DAGs) in a Markov equivalence class is pivotal to infer causal effects or to discover the causal DAG via appropriate interventional data. We consider counting and uniform sampling of DAGs that are Markov equivalent to a given DAG. These problems efficiently reduce to counting the moral acyclic orientations of a given undirected connected chordal graph on n vertices, for which we give two algorithms. Our first algorithm requires O(2(n)n(4)) arithmetic operations, improving a previous super-exponential upper bound. The second requires O (k! 2(k) k(2)n) operations, where k is the size of the largest clique in the graph; for bounded-degree graphs this bound is linear in n. After a single run, both algorithms enable uniform sampling from the equivalence class at a computational cost linear in the graph size. Empirical results indicate that our algorithms are superior to previously presented algorithms over a range of inputs; graphs with hundreds of vertices and thousands of edges are processed in a second on a desktop computer.
  • Roman, Veronica L.; Merlin, Christophe; Virta, Marko P. J.; Bellanger, Xavier (2021)
    EpicPCR (Emulsion, Paired Isolation and Concatenation PCR) is a recent single-cell genomic method based on a fusion-PCR allowing us to link a functional sequence of interest to a 16S rRNA gene fragment and use the mass sequencing of the resulting amplicons for taxonomic assignment of the functional sequence-carrying bacteria. Although it is interesting because it presents the highest efficiency for assigning a bacterial host to a marker, epicPCR remains a complex multistage procedure with technical difficulties that may easily impair the approach depth and quality. Here, we described how to adapt epicPCR to new gene targets and environmental matrices while identifying the natural host range of SXT/R391 integrative and conjugative elements in water microbial communities from the Meurthe River (France). We notably show that adding a supplementary PCR step allowed us to increase the amplicon yield and thus the number of reads obtained after sequencing. A comparison of operational taxonomic unit (OTU) identification approaches when using biological and technical replicates demonstrated that, although OTUs can be validated when obtained from three out of three technical replicates, up to now, results obtained from two or three biological replicates give a similar and even a better confidence level in OTU identification, while allowing us to detect poorly represented SXT/R391 hosts in microbial communities.
  • Zhou, Guo-Wei; Yang, Xiao-Ru; Rønn, Regin; Su, Jian-Qiang; Cui, Li; Zheng, Bang-Xiao; Zhu, Yong-Guan (2019)
    Microorganisms capable of anaerobic nitrate-dependent Fe(II) (ferrous iron) oxidation (ANDFO) contribute significantly to iron and nitrogen cycling in various environments. However, lab efforts in continuous cultivation of ANDFO strains suffer from loss of activity when ferrous iron is used as sole electron donor. Here we used a novel strain of nitrate-dependent Fe(II)-oxidizing bacterium Bacillus ferroxidians as a model and focused on physiological activity of cells during ANDFO. It was shown that B. ferroxidans entered a metabolically inactive state during ANDFO. B. ferrooxidans exhibited nitrate reduction coupled with Fe(II) oxidation, and the activity gradually declined and was hardly detected after 48-h incubation. Propidium monoazide (PMA) assisted 16S rRNA gene real-time PCR suggested that large number of B. ferrooxidans cells were alive during incubation. However, 2H(D)-isotope based Raman analysis indicated that the cells were metabolically inactive after 120-h of ANDFO. These inactive cells re-awakened in R2A medium and were capable of growth and reproduction, which was consistent with results in Raman analysis. Scanning electron microscopy (SEM) observation and x-ray diffraction (XRD) revealed the formation of Fe minerals in close proximity of cells in the Fe(II)-oxidizing medium after Fe(II) oxidation. Overall, our results demonstrated that continued ANDFO can induce a metabolically inactive state in B. ferrooxidans, which was responsible for the loss of activity during ANDFO. This study provides insight into the ANDFO process and its contribution to iron and nitrogen cycling in the environments.