Paper Info
Title
Multithreaded Algorithms for Matching in Graphs with Application to Data Analysis in Flow Cytometry
Abstract
We study parallel algorithms for computing matchings in graphs and apply them to solve population registration problem from bio-imaging data. We have developed several classes of multithreaded algorithms for maximum cardinality matching and achieved good speedups on three shared memory machines on a representative set of large real-world and synthetic graphs. The parallel machines include processors that employ multithreading and cache (Intel Nehalem and AMD Opteron) and massively multithreading and flat memory model (Cray XMT). The bio-imaging application involves registering different cell populations across samples using flow cytometry data. The population registration problem is solved by a generalized edge cover, computed from a weighted matching. We have used this approach to differentiate leukemic cells from healthy ones, and to identify phosphorylation shifts in T cells due to stimulation with an antibody. In current work, we are adapting the concept of consistency used in multiple sequence alignments to the population registration problem for large sample sets.
Year
DOI
Venue
2012
10.1109/IPDPSW.2012.310
IPDPS Workshops
Keywords
Field
DocType
parallel algorithm,multithreaded algorithms,maximum cardinality matching,different cell population,flat memory model,flow cytometry data,large real-world,population registration problem,bio-imaging data,flow cytometry,large sample set,data analysis,bio-imaging application,multithreading,multicore processing,graph theory,parallel algorithms,image registration,antibody,multi threading,bipartite graph,cache,algorithm design and analysis,graph matching,approximation algorithms
Population,Approximation algorithm,Multithreading,Shared memory,Edge cover,Cray XMT,Parallel algorithm,Computer science,Parallel computing,Algorithm,Matching (graph theory),Distributed computing
Conference
ISSN
Citations 
PageRank 
2164-7062
5
0.46
References 
Authors
7
2
Name
Order
Citations
PageRank
Ariful Azad113815.71
Alex Pothen2212.46