Part 2 - Lecture 1 - Global Pairwise Sequence Alignment

Question 1

In global pairwise sequence alignment what does the sequence mean?

Answer 1

could be RNA or Amino acids or DNA (ACGT) - alphabet assumed

Question 2

What are the four criteria to define alignment?

Answer 2

1. one sequence is positioned above the other
2. spaces may be inserted into the sequences
3. spaces may not appear on top of each other
   -after inserting spaces the sequences must have the same length

Question 3

What does global mean in global pairwise sequence alignment?

Answer 3

that we are aligning the entire sequence

Question 4

What does pairwise mean in global pairwise sequence alignment?

Answer 4

we restrict our attention to 2 sequences at a time (in other methods there can be more sequences)

Question 5

Out of these four examples which are alignments and which are not?

Answer 5

-all are alignments except for the top one in the left hand corner cause there are spaces on top of each other

Question 6

What should alignments reveal?

Answer 6

biological relationships

Question 7

Why might we align sequences?

Answer 7

-Do known sequences align well with ours? - check if we discovered a new gene
-What about parts that do not align at all?
-Can gather biological and evolutionary insights from parts that align well

Question 8

What is sequence similarity a strong evidence of?

Answer 8

similar biological function

Question 9

What are some sources of biological differences?

Answer 9

-substitution (point mutation)
-insertion of short sequence/deletion of short sequence (indel) do not know whether something has been inserted in one or deleted in another so call it indel

Question 10

What is a segmental duplication?

Answer 10

duplicated blocks of genomic DNA ranging in size from 1-200kb

Question 11

What is an inversion?

Answer 11

when a section of DNA breaks off and reattaches to the chromosome in reversed order

Question 12

What is a transposition?

Answer 12

a discrete section of DNA is moved from one location in the genome to another

Question 13

What is a translocation?

Answer 13

On piece of chromosome breaks and attached to another chromosome

Question 14

What are some sources of technical differences in alignment?

Answer 14

-sequencing machines make mistakes
-different technologies lead to different errors (illumina has fewer indels an more SNVs and substitutions from PCR)
(PacBIO and Nanopore have greater indels cause they are long strand sequencing)
-PCR is a major factor

Question 15

How to score alignments and what doe high scores indicate?

Answer 15

-high scores indicated better alignments
-each score is assigned to a position separately

-identity (match) = +1
substituion or mismatch = -u
indel = -S

Question 16

What defines the best when we are trying to get the best alignmnt?

Answer 16

modeling and probability and statistics define best

Question 17

What finds the best alignment?

Answer 17

algorithms

Question 18

What is an alignment matrix?

Answer 18

if two sequences have length n and m then we have nm rows and cols with one more row and one more col for an added space at the beginning of each sequence

Question 19

What do alignments correspond to?

Answer 19

paths

Question 20

What does an alignment path look like with scoring?

Answer 20

match is +1
indel is -delta or -1
substitution is -u or -.15

Question 21

How do you calculate the best score for alignment?

Answer 21

1. calculates the best score for prefixes of two sequences
2. update incrementally from there

Question 22

If T is a function that gives the score of the best alignment sequence what is the first step to formalization?

Answer 22

Question 23

What is some formal notation for general recurrence relation?

Answer 23

Question 24

Question 25

What is the average size of the human genome?

Answer 25

3 billion bases

Question 26

Question 27

When we calculate the score in each cell of the matrix how do we keep a record of which neighboring cell we used?

Answer 27

we can represent this as an arrow pointing back, up, or diagonally back and up

Question 28

What does following the arrows allow us to do?

Answer 28

write out the alignment

Question 29

What does moving upward mean?

Answer 29

inserting a space in the sequence written in the top

Question 30

What does moving backward mean?

Answer 30

inserting a space of the sequence on the left

Question 31

What does moving diagonally mean?

Answer 31

no space one letter is on top of the other

Question 32

How do you perform a traceback?

Answer 32

1. start in the bottom right 2. follow the arrows to the top left 3. each arrow adds a position to the alignment 4. moving past a row or column consumes that row or column

Question 33

What is time complexity?

Answer 33

-a function of sequence length - how does the amount of work scale for each individual cell

Question 34

What is the time complexity for global pairwise alignment?

Answer 34

time complexity is O(n^2) if you compute n^2 entries in the matrix for length n sequences -the amount of work for each individual cell is constant we need to look at all three instance and decide score based on that for each cell

Question 35

What is space complexity?

Answer 35

the space we need is proportional to the size of the alignment matrix all values must be stored

Question 36

What is the space complexity for global pairwise alignment?

Answer 36

the required space is quadratic because it is a function that scales like the square of the length of the sequences O(n^2)

Question 37

What is never less than the space complexity?

Answer 37

time complexity - since every time we do work we store it and take up space