Parallel color-coding

George M. Slota; Kamesh Madduri

doi:10.1016/j.parco.2015.02.004

Parallel color-coding

George M. Slota, Kamesh Madduri

Research output: Contribution to journal › Article › peer-review

11 Scopus citations

Abstract

Abstract We present new parallelization and memory-reducing strategies for the graph-theoretic color-coding approximation technique, with applications to biological network analysis. Color-coding is a technique that gives fixed parameter tractable algorithms for several well-known NP-hard optimization problems. In this work, by efficiently parallelizing steps in color-coding, we create two new biological protein interaction network analysis tools: Fascia for subgraph counting and motif finding and FastPath for signaling pathway detection. We demonstrate considerable speedup over prior work, and the optimizations introduced in this paper can also be used for other problems where color-coding is applicable.

Original language	English (US)
Article number	2236
Pages (from-to)	51-69
Number of pages	19
Journal	Parallel Computing
Volume	47
DOIs	https://doi.org/10.1016/j.parco.2015.02.004
State	Published - Aug 4 2015

All Science Journal Classification (ASJC) codes

Software
Theoretical Computer Science
Hardware and Architecture
Computer Networks and Communications
Computer Graphics and Computer-Aided Design
Artificial Intelligence

Access to Document

10.1016/j.parco.2015.02.004

Cite this

@article{e35ee0404f2542cc8c073b149adfee2a,

title = "Parallel color-coding",

abstract = "Abstract We present new parallelization and memory-reducing strategies for the graph-theoretic color-coding approximation technique, with applications to biological network analysis. Color-coding is a technique that gives fixed parameter tractable algorithms for several well-known NP-hard optimization problems. In this work, by efficiently parallelizing steps in color-coding, we create two new biological protein interaction network analysis tools: Fascia for subgraph counting and motif finding and FastPath for signaling pathway detection. We demonstrate considerable speedup over prior work, and the optimizations introduced in this paper can also be used for other problems where color-coding is applicable.",

author = "Slota, {George M.} and Kamesh Madduri",

note = "Funding Information: This research is part of the Blue Waters sustained-petascale computing project, which is supported by the National Science Foundation (awards OCI-0725070 , ACI-1238993 , and ACI-1444747 ) and the state of Illinois. Blue Waters is a joint effort of the University of Illinois at Urbana-Champaign and its National Center for Supercomputing Applications. This work is also supported by NSF grants ACI-1253881 , CCF-1439057 , and the DOE Office of Science through the FASTMath SciDAC Institute . Sandia National Laboratories is a multi-program laboratory managed and operated by Sandia Corporation, a wholly owned subsidiary of Lockheed Martin Corporation, for the U.S. Department of Energy{\textquoteright}s National Nuclear Security Administration under contract DE-AC04–94AL85000. Publisher Copyright: {\textcopyright} 2015 Elsevier B.V.",

year = "2015",

month = aug,

day = "4",

doi = "10.1016/j.parco.2015.02.004",

language = "English (US)",

volume = "47",

pages = "51--69",

journal = "Parallel Computing",

issn = "0167-8191",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Parallel color-coding

AU - Slota, George M.

AU - Madduri, Kamesh

N1 - Funding Information: This research is part of the Blue Waters sustained-petascale computing project, which is supported by the National Science Foundation (awards OCI-0725070 , ACI-1238993 , and ACI-1444747 ) and the state of Illinois. Blue Waters is a joint effort of the University of Illinois at Urbana-Champaign and its National Center for Supercomputing Applications. This work is also supported by NSF grants ACI-1253881 , CCF-1439057 , and the DOE Office of Science through the FASTMath SciDAC Institute . Sandia National Laboratories is a multi-program laboratory managed and operated by Sandia Corporation, a wholly owned subsidiary of Lockheed Martin Corporation, for the U.S. Department of Energy’s National Nuclear Security Administration under contract DE-AC04–94AL85000. Publisher Copyright: © 2015 Elsevier B.V.

PY - 2015/8/4

Y1 - 2015/8/4

N2 - Abstract We present new parallelization and memory-reducing strategies for the graph-theoretic color-coding approximation technique, with applications to biological network analysis. Color-coding is a technique that gives fixed parameter tractable algorithms for several well-known NP-hard optimization problems. In this work, by efficiently parallelizing steps in color-coding, we create two new biological protein interaction network analysis tools: Fascia for subgraph counting and motif finding and FastPath for signaling pathway detection. We demonstrate considerable speedup over prior work, and the optimizations introduced in this paper can also be used for other problems where color-coding is applicable.

AB - Abstract We present new parallelization and memory-reducing strategies for the graph-theoretic color-coding approximation technique, with applications to biological network analysis. Color-coding is a technique that gives fixed parameter tractable algorithms for several well-known NP-hard optimization problems. In this work, by efficiently parallelizing steps in color-coding, we create two new biological protein interaction network analysis tools: Fascia for subgraph counting and motif finding and FastPath for signaling pathway detection. We demonstrate considerable speedup over prior work, and the optimizations introduced in this paper can also be used for other problems where color-coding is applicable.

UR - http://www.scopus.com/inward/record.url?scp=84938419458&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84938419458&partnerID=8YFLogxK

U2 - 10.1016/j.parco.2015.02.004

DO - 10.1016/j.parco.2015.02.004

M3 - Article

AN - SCOPUS:84938419458

SN - 0167-8191

VL - 47

SP - 51

EP - 69

JO - Parallel Computing

JF - Parallel Computing

M1 - 2236

ER -

Parallel color-coding

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this