2. Big data

Question 1

How to improve a task (memory requirement / speed)?

Answer 1

• fast computer?

next three tied together:
* algorithm - appropriate & efficient
* data structure - efficient to use/access/query, space efficient to store
* parallelization - to split up tasks and run in parallel

Question 2

Most realistic time complexity for algorithms in sequence bioinformatics ?

Answer 2

exponential; polynomial

Question 3

Define time complexity

examples?

Answer 3

Time complexity is defined as the amount of time taken by an algorithm to run, as a function of the length of the input.

= how does the running time of an algorithm increase
with the size of the input?

= most useful way to measure effectiveness of an algorithm

eg. constant, logarithmic, linear, polynomial, exponential

Question 4

Algorithms - classifications? + examples

Answer 4

by complexity
* logarithmic, linear, quadratic, polynomial, etc

… by design
* brute force
* heuristic (zB greedy, seed and extend
* recursion (dynamic programming)

… by data structure
* hash table
* graphs (zB trees)

… by (biological) problem
* pattern search

Question 5

Brute force algorithm?
- definition
- use
- running time

Answer 5

• try all possibilities to find the optimal solution –> output: the optimal solution
• can only be used for small problems in bioinformatics
• often have exponential running time

Question 6

Heuristic algorithm?
- definition
- use

Answer 6

don’t guarantee that the optimal solution is found, because not all solutions are evaluated

are a good compromise between speed and accuracy

many different types / designs exist and are used

Question 7

Two examples for heuristic algorithms

Answer 7

• greedy algorithms
• seed-and-extend = seed-and-filter-and-extend

Question 8

Greedy logarithm - definition, use ?

Answer 8

• Heuristic logarithm
• at each step, the algorithm takes the best immediate solution while finding an answer –> may not find the best possible overall solution
• used for optimization problems
• used for sequence alignment & assembly, phylogenetic inference, etc

Question 9

Seed-and-extend
definition, use?

Answer 9

Seed-and-extend = seed-and-filter-and-extend

• observation: true matches contain short, exactly matching kmers (seeds)
• these are easy & fast to find (compared to longer / inexact matches), as can exclude any point mutations
• extend these short matches in a second step, and only these (filter)
• used for alignment

Question 10

Subsampling of k-mers - name 3 types?

Answer 10

minimizers, syncmers, strobemers

Question 11

Subsampling - Minimizers?

Answer 11

saves on space /ram

such that the same k-mers will be selected from similar sequences

doi:10.1093/bioinformatics/bth408

Question 12

Subsampling - syncmers?

Answer 12

within a window, select the k-mer(s) with the smallest s-mer at the start or end
- suited for comparison of seqs with mismatches

https://doi.org/10.7717/peerj.10805

Question 13

Data structure - definition, common examples?

Answer 13

• “the organization of information such that it can be
  used efficiently”
• common data structures: hash table, string, list, table, (suffix) tree, graph

Question 14

Suffix tree - definition, use?

Answer 14

• representation of a string - present the suffixes of a given string in a tree
• edges are labeled with strings, such that each suffix of a string corresponds to exactly one path from the root to a leaf
  *allows efficient searching of this text present the suffixes of a given string in a tree

Question 15

Suffix tree - disadvantages / advantages?

Answer 15

disadvantages
* not so efficient to construct
* not so efficient to store
(–> convert to more space-efficient suffix arrays!)

advantages
* very efficient to search
- search is proportional to length of the pattern

Question 16

Suffix trees - applications?

Answer 16

many applications in sequence bioinformatics
- keywords/patterns in text
- (maximal) repeats
- unique substrings
- longest common substring
- inexact matches

Question 18

Parallelization - why? requires? types?

Answer 18

(parallel computing as opposed to serial computing)

why
* clock speed maxed out
* performance improvements now only possible through parallelization

requires
* special hardware and programs
* important: frequent communication between subtasks?

types
* embarrassing, coarse-grained, fine-grained

Question 19

multi-core computers - where? why? requires?

Answer 19

• many-core processors are standard now - desktops, laptops, mobile phones, …
• communication between cores is fast / easy
• required rewriting of software (parameters)

Question 20

(computing) clusters - definition/ consists of, disadvantage, requires, example in linux

Answer 20

definition / consists of:
* multiple computers (that are multi-core); nodes
* a login / head / master node
* linked by a fast local area network

disadvantage:
* expensive – but cheaper than a single computer of comparable size & speed

requires:
* application programs: extra programming / parameters
* requires a system to distribute jobs

example in linux:
SLURM

Question 21

Heterogeneous computing

Answer 21

CPUs
* 2-8 cores, general-purpose

GPUs
* hundreds of cores, highly specialized - thanks to gaming!
* programmable for general purpose computing since 2007: CUDA (NVIDIA)

integration of CPUs and GPUs
–> performance boost
but: specialized programs / programming skills required

Question 22

cloud computing - definition, advantages, example providors, requirments

Answer 22

definition: virtual machines on many networked computers
advantages:
- emulation of a physical computer (operating system, configuration, software, etc)
- high flexibility
- saving & duplicating a VM is very easy

computing power rented on demand - example:
- Amazon, Google, Microsoft
- some biological data sets available;

limiting step: data upload may otherwise be the limiting step

requires:
- specialized programming required
MapReduce / Hadoop; Go programming language

Question 23

Big data - skills needed?

Answer 23

• know, understand, select efficient & appropriate
  algorithms
• efficient run time for large data sets
• efficient memory usage
• efficient data structures
  (space efficient, efficient to access)
• be able to work on high performance computers
• remote computing
• parallel computing
• organize data / results / documentation
• learn to work with many different programs
• work under unix/linux, in the terminal

Question 24

Algorithm - definition

Answer 24

a list set of instructions, used to solve problems or perform tasks

input –>** algorithm **–> output

• a sequence of ordered instructions that must be carried out to solve a well-formulated problem
• algorithms can be stated in English (or German or Spanish) or in pseudocode
• algorithms can be implemented in different ways (e.g., in different programming languages)
• a correct algorithm will solve all instances of a problem
• given a problem, there may be many correct algorithms that can solve it

Question 25

Connection between data structure and algorithm?

Answer 25

• Algorithms: complexity/efficiency: one factor for this is space requirement, which can be optimised by using the right data structures
• The way the data is accessed by the algorithm differs depending on the data structure