Biology subjects

Boucher, C.

Publications and source records attributed to Boucher, C..

5 recordsLinked to original sources

bioRxiv2018

Identification of co-evolving temporal networks

MotivationBiological networks describes the mechanisms which govern cellular functions. Temporal networks show how these networks evolve over time. Studying the temporal progression of network topologies is of utmost importance since it uncovers how a network evolves and how it resists to external stimuli and internal variations. Two temporal networks have co-evolving subnetworks if the topologies of these subnetworks remain similar to each other as the network topology evolves over a period of time. In this paper, we consider the problem of identifying co-evolving pair of temporal networks, which aim to capture the evolution of molecules and their interactions over time. Although this problem shares some characteristics of the well-known network alignment problems, it differs from existing network alignment formulations as it seeks a mapping of the two network topologies that is invariant to temporal evolution of the given networks. This is a computationally challenging problem as it requires capturing not only similar topologies between two networks but also their similar evolution patterns.\n\nResultsWe present an efficient algorithm, Tempo, for solving identifying coevolving subnetworks with two given temporal networks. We formally prove the correctness of our method. We experimentally demonstrate that Tempo scales efficiently with the size of network as well as the number of time points, and generates statistically significant alignments--even when evolution rates of given networks are high. Our results on a human aging dataset demonstrate that Tempo identifies novel genes contributing to the progression of Alzheimers, Huntingtons and Type II diabetes, while existing methods fail to do so.\n\nAvailabilitySoftware is available online (https://www.cise.ufi.edu/[~]relhesha/temporal.zip).\n\nContactrelhesha@ufi.edu\n\nSupplementary informationSupplementary data are available at Bioinformatics online.

bioinformatics↗

bioRxiv2018

Error Correcting Optical Mapping Data

Optical mapping is a unique system that is capable of producing high-resolution, high-throughput genomic map data that gives information about the structure of a genome [21]. Recently it has been used for scaffolding contigs and assembly validation for large-scale sequencing projects, including the maize [32], goat [6], and amborella [4] genomes. However, a major impediment in the use of this data is the variety and quantity of errors in the raw optical mapping data, which are called Rmaps. The challenges associated with using Rmap data are analogous to dealing with insertions and deletions in the alignment of long reads. Moreover, they are arguably harder to tackle since the data is numerical and susceptible to inaccuracy. We develop cOMet to error correct Rmap data, which to the best of our knowledge is the only optical mapping error correction method. Our experimental results demonstrate that cOMet has high prevision and corrects 82.49% of insertion errors and 77.38% of deletion errors in Rmap data generated from the E. coli K-12 reference genome. Out of the deletion errors corrected, 98.26% are true errors. Similarly, out of the insertion errors corrected, 82.19% are true errors. It also successfully scales to large genomes, improving the quality of 78% and 99% of the Rmaps in the plum and goat genomes, respectively. Lastly, we show the utility of error correction by demonstrating how it improves the assembly of Rmap data. Error corrected Rmap data results in an assembly that is more contiguous, and covers a larger fraction of the genome.

bioinformatics↗

bioRxiv2017

Succinct De Bruijn Graph Construction for Massive Populations Through Space-Efficient Merging

Recently, there has been significant amount of effort in developing space-efficient and succinct data structures for storing and building the traditional de Bruijn graph and its variants, including the colored de Bruijn graph. However, a problem not yet considered is developing a means to merge succinct representations of the de Bruijn graph--a challenge is necessary for constructing the de Bruijn graph on very-large datasets. We create VO_SCPLOWARIC_SCPLOWMO_SCPLOWERGEC_SCPLOW, for building the colored de Bruijn graph on a very-large dataset through partitioning the data into smaller subsets, building the colored de Bruijn graph using a FM-index based representation, and merging these representations in an iterative format. This last step is an algorithmic challenge for which we present an algorithm in this paper. Lastly, we demonstrate the utility of VO_SCPLOWARIC_SCPLOWMO_SCPLOWERGEC_SCPLOW by demonstrating: a four-fold reduction in working space when constructing an 8,000 color dataset, and the construction of population graph two orders of magnitude larger than previous reported methods.

bioinformatics↗

bioRxiv2017

Resistome SNP Calling via Read Colored de Bruijn Graphs

MotivationThe resistome, which refers to all of the antimicrobial resistance (AMR) genes in pathogenic and non-pathogenic bacteria, is frequently studied using shotgun metagenomic data [14, 47]. Unfortunately, few existing methods are able to identify single nucleotide polymorphisms (SNPs) within metagenomic data, and to the best of our knowledge, no methods exist to detect SNPs within AMR genes within the resistome. The ability to identify SNPs in AMR genes across the resistome would represent a significant advance in understanding the dissemination and evolution of AMR, as SNP identification would enable \"fingerprinting\" of the resistome, which could then be used to track AMR dynamics across various settings and/or time periods.\n\nResultsWe present LueVari, a reference-free SNP caller based on the read colored de Bruijn graph, an extension of the traditional de Bruijn graph that allows repeated regions longer than the k-mer length and shorter than the read length to be identified unambiguously. We demonstrate LueVari was the only method that had reliable sensitivity (between 73% and 98%) as the performance of competing methods varied widely. Furthermore, we show LueVari constructs sequences containing the variation which span 93% of the gene in datasets with lower coverage (15X), and 100% of the gene in datasets with higher coverage (30X).\n\nAvailabilityCode and datasets are publicly available at https://github.com/baharpan/cosmo/tree/LueVari.

bioinformatics↗

bioRxiv2016

Disentangled Long-Read De Bruijn Graphs via Optical Maps

Pacific Biosciences (PacBio), the main third generation sequencing technology can produce scalable, high-throughput, unprecedented sequencing results through long reads with uniform coverage. Although these long reads have been shown to increase the quality of draft genomes in repetitive regions, fundamental computational challenges remain in overcoming their high error rate and assembling them efficiently. In this paper we show that the de Bruijn graph built on the long reads can be efficiently and substantially disentangled using optical mapping data as auxiliary information. Fundamental to our approach is the use of the positional de Bruijn graph and a succinct data structure for constructing and traversing this graph. Our experimental results show that over 97.7% of directed cycles have been removed from the resulting positional de Bruijn graph as compared to its non-positional counterpart. Our results thus indicate that disentangling the de Bruijn graph using positional information is a promising direction for developing a simple and efficient assembly algorithm for long reads.

bioinformatics↗