Mahmoud Parsian - Data Algorithms: Recipes for Scaling Up with Hadoop and Spark

• 2015-07-10: First Release

Unlocking the power of the genome is a powerful notion one that intimates knowledge, understanding, and the ability of science and technology to be transformative. But transformation requires alignment and synergy, and synergy almost always requires deep collaboration. From scientists to software engineers, and from academia into the clinic, we will need to work together to pave the way for our genetically empowered future.

The creation of data algorithms that analyze the information generated from large-scale genetic sequencing studies is key. Genetic variations are diverse; they can be complex and novel, compounded by a need to connect them to an individuals physical presentation in a meaningful way for clinical insights to be gained and applied. Accelerating our ability to do this at scale, across populations of individuals, is critical. The methods in this book serve as a compass for the road ahead.

MapReduce, Hadoop, and Spark are key technologies that will help us scale the use of genetic sequencing, enabling us to store, process, and analyze the big data of genomics. Mahmouds book covers these topics in a simple and practical manner. Data Algorithms illuminates the way for data scientists, software engineers, and ultimately clinicians to unlock the power of the genome, helping to move human health into an era of precision, personalization, and transformation.

Jay Flatley

CEO, Illumina Inc.

With the development of massive search engines (such as Google and Yahoo!), genomic analysis (in DNA sequencing, RNA sequencing, and biomarker analysis), and social networks (such as Facebook and Twitter), the volumes of data being generated and processed have crossed the petabytes threshold. To satisfy these massive computational requirements, we need efficient, scalable, and parallel algorithms. One framework to tackle these problems is the MapReduce paradigm.

MapReduce is a software framework for processing large (giga-, tera-, or petabytes) data sets in a parallel and distributed fashion, and an execution framework for large-scale data processing on clusters of commodity servers. There are many ways to implement MapReduce, but in this book our primary focus will be Apache Spark and MapReduce/Hadoop. You will learn how to implement MapReduce in Spark and Hadoop through simple and concrete examples.

This book provides essential distributed algorithms (implemented in MapReduce, Hadoop, and Spark) in the following areas, and the chapters are organized accordingly :

• Basic design patterns
• Data mining and machine learning
• Bioinformatics, genomics, and statistics
• Optimization techniques

What Is MapReduce?

] implementation is a proprietary solution and has not yet been released to the public.

A simple view of the MapReduce process is illustrated in . Simply put, MapReduce is about scalability. Using the MapReduce paradigm, you focus on writing two functions:

map()

Filters and aggregates data

reduce()

Reduces, groups, and summarizes by keys generated by map()

Figure P-1. The simple view of the MapReduce process

These two functions can be defined as follows:

map() function

The master node takes the input, partitions it into smaller data chunks, and distributes them to worker (slave) nodes. The worker nodes apply the same transformation function to each data chunk, then pass the results back to the master node. In MapReduce, the programmer defines a mapper with the following signature :

map():(Key1,Value1)[(Key2,Value2)]

reduce() function

The master node shuffles and clusters the received results based on unique key-value pairs; then, through another redistribution to the workers/slaves, these values are combined via another type of transformation function. In MapReduce, the programmer defines a reducer with the following signature:

reduce():(Key2,[Value2])[(Key3,Value3)]

---

Note

In informal presentations of the map() and reduce() functions throughout this book, Ive used square brackets, [], to denote a list.

---

In .

Table P-1. Mappers output

Key	Value
K1	V11
K2	V21
K1	V12
K2	V22
K2	V23

In this example, all mappers generate only two unique keys: {K1, K2}. When all mappers are completed, the keys are sorted, shuffled, grouped, and sent to reducers. Finally, the reducers generate the desired outputs. For this example, we have two reducers identified by {K1, K2} keys (illustrated by ).

Table P-2. Reducers input