NDLI: Parallel analysis of large graph-structured data in genomics and proteomics

Content Provider	IEEE Xplore Digital Library
Author	Madduri, K.
Copyright Year	2013
Description	Author affiliation: Dept. of Comput. Sci. & Eng., Pennsylvania State Univ., University Park, PA, USA (Madduri, K.)
Abstract	This talk presents two new software tools that our research group is developing: lark, a de novo genome assembler, and FASCIA, a tool to approximately count and enumerate network motifs. Our de novo genome assembly approach involves construction, traversal, and simplification of de Bruijn graphs on large multicore clusters. We present new parallelization strategies and optimizations for various steps of the assembly process, focusing on techniques for scalable de Bruijn graph construction from short-read data. We demonstrate the parallel efficiency and scalability of our assembler with performance results and analysis of several recent metagenomic data sets. The problem of subgraph counting refers to determining the frequency of occurrence of a given subgraph or template within a large network. Subgraph counting is used to detect and characterize local structure (network motifs) in several biological networks, including protein interaction networks and metabolic networks. Exhaustive enumeration and exact counting is extremely compute-intensive, with running time growing exponentially with the number of vertices in the template. In FASCIA, we combine parallelism with the color coding technique to determine approximate counts of non-induced occurrences of the subgraph in the original network. The color coding technique gives a fast approximate algorithm for this problem, using a dynamic programming-based counting approach. Our new contributions are a multilevel shared-memory parallelization of the counting scheme and several optimizations to reduce the memory footprint. We show that approximate counts can be obtained for templates with up to 12 vertices, on networks with up to millions of vertices and edges.
Starting Page	1
Ending Page	1
File Size	22529
Page Count	1
File Format	PDF
ISBN	9781479907168
DOI	10.1109/ICCABS.2013.6629240
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2013-06-12
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Image color analysis Genomics Educational institutions Fascia Bioinformatics Assembly Optimization
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

De novo co-assembly of bacterial genomes from multiple single cells

Efficient algorithms for sequence assembly

Workshop: Graph compression approaches in assembly

Parallel architecture and hardware implementation of pre-processor and post-processor for sequence assembly

Workshop: An efficient data structure for exact-match overlap graphs and next generation sequence assembly

Workshop: Comparative assembly of metagenomic sequences

Identifying context-specific transcription factor targets from prior knowledge and gene expression data

Multi-graph-view Learning for Graph Classification

Supersonic MiB

Parallel analysis of large graph-structured data in genomics and proteomics

Similar Documents

De novo co-assembly of bacterial genomes from multiple single cells

Efficient algorithms for sequence assembly

Workshop: Graph compression approaches in assembly

Parallel architecture and hardware implementation of pre-processor and post-processor for sequence assembly

Workshop: An efficient data structure for exact-match overlap graphs and next generation sequence assembly

Workshop: Comparative assembly of metagenomic sequences

Identifying context-specific transcription factor targets from prior knowledge and gene expression data

Multi-graph-view Learning for Graph Classification

Supersonic MiB

Parallel analysis of large graph-structured data in genomics and proteomics