SCHEDULE: NOV 15-20, 2015

When viewing the Technical Program schedule, on the far righthand side is a column labeled "PLANNER." Use this planner to build your own schedule. Once you select an event and want to add it to your personal schedule, just click on the calendar icon of your choice (outlook calendar, ical calendar or google calendar) and that event will be stored there. As you select events in this manner, you will have your own schedule to guide you through the week.

Parallel Distributed Memory Construction of Suffix and Longest Common Prefix Arrays

SESSION: Applications: Biophysics and Genomics

EVENT TYPE: Papers, Best Student Paper Finalists

TIME: 2:30PM - 3:00PM

SESSION CHAIR(S): Amanda Randles

AUTHOR(S):Patrick Flick, Srinivas Aluru

ROOM:18AB

ABSTRACT:

Suffix arrays and trees are fundamental string data structures of importance to
many applications in computational biology. Consequently, their parallel
construction is an actively studied problem. To date, algorithms with best
practical performance lack efficient worst-case run-time guarantees, and vice
versa. In addition, much of the recent work targeted low core count, shared
memory parallelization. In this paper, we present parallel algorithms for
distributed memory construction of suffix arrays and longest common prefix (LCP)
arrays that simultaneously achieve good worst-case run-time bounds and superior
practical performance. Our algorithms run in O(T_sort(n,p)log(n)) worst-case
time where T_sort(n,p) is the run-time of parallel sorting. We present
several algorithm engineering techniques that improve performance in practice.
We demonstrate the constructions of suffix and LCP arrays of the human genome in
less than 8 seconds on 1,024 Intel Xeon cores, reaching speedups of over 110X
compared to the best sequential suffix array construction implementation
divsufsort.

Chair/Author Details:

Amanda Randles (Chair) - Duke University|

Patrick Flick - Georgia Institute of Technology

Srinivas Aluru - Georgia Institute of Technology

  Click here to download .ics calendar file

  Click here to download .vcs calendar file

  Click here to add event to your Google Calendar

Paper provided by the ACM Digital Library

Paper also available from IEEE Computer Society