More Like this

1. Cuttlefish: fast, parallel and low-memory compaction of de Bruijn graphs from large-scale genome collections

   https://doi.org/10.1093/bioinformatics/btab309  

   Khan, Jamshed ; Patro, Rob ( July 2021 , Bioinformatics)

   null (Ed.)

   Abstract Motivation The construction of the compacted de Bruijn graph from collections of reference genomes is a task of increasing interest in genomic analyses. These graphs are increasingly used as sequence indices for short- and long-read alignment. Also, as we sequence and assemble a greater diversity of genomes, the colored compacted de Bruijn graph is being used more and more as the basis for efficient methods to perform comparative genomic analyses on these genomes. Therefore, time- and memory-efficient construction of the graph from reference sequences is an important problem. Results We introduce a new algorithm, implemented in the tool Cuttlefish, to construct the (colored) compacted de Bruijn graph from a collection of one or more genome references. Cuttlefish introduces a novel approach of modeling de Bruijn graph vertices as finite-state automata, and constrains these automata’s state-space to enable tracking their transitioning states with very low memory usage. Cuttlefish is also fast and highly parallelizable. Experimental results demonstrate that it scales much better than existing approaches, especially as the number and the scale of the input references grow. On a typical shared-memory machine, Cuttlefish constructed the graph for 100 human genomes in under 9 h, using ∼29 GB of memory. On 11 diverse conifer plant genomes, the compacted graph was constructed by Cuttlefish in under 9 h, using ∼84 GB of memory. The only other tool completing these tasks on the hardware took over 23 h using ∼126 GB of memory, and over 16 h using ∼289 GB of memory, respectively. Availability and implementation Cuttlefish is implemented in C++14, and is available under an open source license at https://github.com/COMBINE-lab/cuttlefish. Supplementary information Supplementary data are available at Bioinformatics online. 

   more » « less
2. phenotools: An r package for visualizing and analysing phenomic datasets

   https://doi.org/10.1111/2041-210X.13217  

   Eliason, Chad M. ; Edwards, Scott V. ; Clarke, Julia A. ( July 2019 , Methods in Ecology and Evolution)

   Phenotypic data are crucial for understanding genotype–phenotype relationships, assessing the tree of life and revealing trends in trait diversity over time. Large‐scale description of whole organisms for quantitative analyses (phenomics) presents several challenges, and technological advances in the collection of genomic data outpace those for phenomic data. Reasons for this disparity include the time‐consuming and expensive nature of collecting discrete phenotypic data and mining previously published data on a given species (both often requiring anatomical expertise across taxa), and computational challenges involved with analysing high‐dimensional datasets.

   One approach to building approximations of organismal phenomes is to combine published datasets of discrete characters assembled for phylogenetic analyses into a phenomic dataset. Despite a wealth of legacy datasets in the literature for many groups, relatively few methods exist for automating the assembly, analysis, and visualization of phenomic datasets in phylogenetic contexts. Here, we introduce a newrpackagephenotoolsfor integrating (fusing original or legacy datasets), curating (finding and removing duplicates) and visualizing phenomic datasets.

   We demonstrate the utility of the proposed toolkit with a morphological dataset for flightless birds and two morphological datasets for theropod dinosaurs and provide recommendations for character construction to maximize accessibility in future workflows. Visualization tools allow rapid identification of anatomical subregions with difficult or problematic histories of homology.

   We anticipate these tools aiding automation of the assembly and visualization of phenomic datasets to inform evolutionary relationships and rates of phenotypic evolution.

    

   more » « less
3. Evidence for population genetic structure in two exploited Mekong River fishes across a natural riverine barrier

   https://doi.org/10.1111/jfb.14424  

   Biesack, Ellen E. ; Dang, Binh T. ; Ackiss, Amanda S. ; Bird, Christopher E. ; Chheng, Phen ; Phounvisouk, Latsamy ; Truong, Oanh T. ; Carpenter, Kent E. ( July 2020 , Journal of Fish Biology)

   Impacts of urban development on aquatic populations are often complex and difficult to ascertain, but population genetic analysis has allowed researchers to monitor and estimate gene flow in the context of existing and future hydroelectric projects. The Lower Mekong Basin is undergoing rapid hydroelectric development with around 50 completed and under‐construction dams and 95 planned dams. The authors investigated the baseline genetic diversity of two exploited migratory fishes, the mud carpHenicorhynchus lobatus(five locations), and the rat‐faced pangasiid catfish,Helicophagus leptorhynchus(two locations), in the Lower Mekong Basin using the genomic double digest restriction site‐associated DNA (ddRAD) sequencing method. In both species, fish sampled upstream of Khone Falls were differentiated from those collected at other sites, andN_eestimates at the site above the falls were lower than those at other sites. This was the first study to utilize thousands of RAD‐generated single nucleotide polymorphisms to indicate that the Mekong's Khone Falls are a potential barrier to gene flow for these two moderately migratory species. The recent completion of the Don Sahong dam across one of the only channels for migratory fishes through Khone Falls may further exacerbate signatures of isolation and continue to disrupt the migration patterns of regionally vital food fishes. In addition,H. lobatuspopulations downstream of Khone Falls, including the 3S Basin and Tonle Sap system, displayed robust connectivity. Potential obstruction of migration pathways between these river systems resulting from future dam construction may limit dispersal, which has led to elevated inbreeding rates and even local extirpation in other fragmented riverine species.

    

   more » « less
4. GeoGraph: A Framework for Graph Processing on Geometric Data

   https://doi.org/10.1145/3469379.3469384  

   Wang, Yiqiu ; Yu, Shangdi ; Dhulipala, Laxman ; Gu, Yan ; Shun, Julian ( June 2021 , ACM SIGOPS Operating Systems Review)

   In many applications of graph processing, the input data is often generated from an underlying geometric point data set. However, existing high-performance graph processing frameworks assume that the input data is given as a graph. Therefore, to use these frameworks, the user must write or use external programs based on computational geometry algorithms to convert their point data set to a graph, which requires more programming effort and can also lead to performance degradation. In this paper, we present our ongoing work on the Geo- Graph framework for shared-memory multicore machines, which seamlessly supports routines for parallel geometric graph construction and parallel graph processing within the same environment. GeoGraph supports graph construction based on k-nearest neighbors, Delaunay triangulation, and b-skeleton graphs. It can then pass these generated graphs to over 25 graph algorithms. GeoGraph contains highperformance parallel primitives and algorithms implemented in C++, and includes a Python interface. We present four examples of using GeoGraph, and some experimental results showing good parallel speedups and improvements over the Higra library. We conclude with a vision of future directions for research in bridging graph and geometric data processing. 

   more » « less
5. Probabilistic convergence and stability of random mapper graphs

   https://doi.org/10.1007/s41468-020-00063-x  

   Brown, Adam ; Bobrowski, Omer ; Munch, Elizabeth ; Wang, Bei ( March 2021 , Journal of Applied and Computational Topology)

   null (Ed.)

   Abstract We study the probabilistic convergence between the mapper graph and the Reeb graph of a topological space $${\mathbb {X}}$$ X equipped with a continuous function $$f: {\mathbb {X}}\rightarrow \mathbb {R}$$ f : X → R . We first give a categorification of the mapper graph and the Reeb graph by interpreting them in terms of cosheaves and stratified covers of the real line $$\mathbb {R}$$ R . We then introduce a variant of the classic mapper graph of Singh et al. (in: Eurographics symposium on point-based graphics, 2007), referred to as the enhanced mapper graph, and demonstrate that such a construction approximates the Reeb graph of $$({\mathbb {X}}, f)$$ ( X , f ) when it is applied to points randomly sampled from a probability density function concentrated on $$({\mathbb {X}}, f)$$ ( X , f ) . Our techniques are based on the interleaving distance of constructible cosheaves and topological estimation via kernel density estimates. Following Munch and Wang (In: 32nd international symposium on computational geometry, volume 51 of Leibniz international proceedings in informatics (LIPIcs), Dagstuhl, Germany, pp 53:1–53:16, 2016), we first show that the mapper graph of $$({\mathbb {X}}, f)$$ ( X , f ) , a constructible $$\mathbb {R}$$ R -space (with a fixed open cover), approximates the Reeb graph of the same space. We then construct an isomorphism between the mapper of $$({\mathbb {X}},f)$$ ( X , f ) to the mapper of a super-level set of a probability density function concentrated on $$({\mathbb {X}}, f)$$ ( X , f ) . Finally, building on the approach of Bobrowski et al. (Bernoulli 23 (1):288–328, 2017b), we show that, with high probability, we can recover the mapper of the super-level set given a sufficiently large sample. Our work is the first to consider the mapper construction using the theory of cosheaves in a probabilistic setting. It is part of an ongoing effort to combine sheaf theory, probability, and statistics, to support topological data analysis with random data. 

   more » « less