1 of 60

SEQUENCE ALIGNMENT

2 of 60

WHICH PAIR IS MORE SIMILAR

I hate your cup

I have your cup

I love your cup

I love his phone

3 of 60

WHAT IS SEQUENCE ALIGNMENT

  • Comparing DNA, RNA, or protein sequences to identify regions of similarity
  • Consequence of functional, structural, or evolutionary relationships between the sequences.
  • Types of sequence alignment
    • Pairwise sequence alignment VS Multiple sequence alignment
    • Global sequence alignment VS Local sequence alignment

4 of 60

WHAT WE WANT TO ACHIEVE FROM ALIGNMENT IN INFORMATICS ASPECT

  • Longest Common Subsequence
  • Subsequence is a part of the input sequence

Bio

Bioinformatics

Informatics

Info

5 of 60

LONGEST COMMON SUBSEQUENCE (LCS)

Bio

Bioinformatics

Informatics

Info

ATTCCTGGAGC

ATTCCTG

ATTCCTGGAGC

ATTCCTGTGCC

6 of 60

WE NEED GAPS

ATTCCTGGAGC

GATTCCTGGC

GAPS

ATTCCTGGAGC

GATTCCTGG C

7 of 60

EXERCISE 1

  • Sequence 1: Jonathan
  • Sequence 2: Joseph

JONATHAN

JOSEPH

8 of 60

EXERCISE 2

  • Sequence 1:Algorithm
  • Sequence 2: Alignment

AL GORITHM

ALI GN MENT

AL GORI THM

ALI GNMENT

9 of 60

HOW TO COMPUTE LCS

a: sequence 1

b: sequence 2

i and j: position

Dynamic algorithm

10 of 60

GCCCTAGCG

GCGC AATG

11 of 60

​

​

T

G

C

T

C

G

T

A

​

0

0

0

0

0

0

0

0

0

T

0

​

​

​

​

​

​

​

​

T

0

​

​

​

​

​

​

​

​

C

0

​

​

​

​

​

​

​

​

A

0

​

​

​

​

​

​

​

​

T

0

​

​

​

​

​

​

​

​

A

0

​

​

​

​

​

​

​

​

12 of 60

​

​

T

G

C

T

C

G

T

A

​

0

0

0

0

0

0

0

0

0

T

0

1

1

1

1

1

1

1

1

T

0

1

1

1

2

2

2

2

2

C

0

1

1

2

2

3

3

3

3

A

0

1

1

2

2

3

3

3

4

T

0

1

1

2

3

3

3

4

4

A

0

1

1

2

3

3

3

4

5

TGCTCGTA

T TCATA

13 of 60

ALIGNMENT RULES

ATTCCTGGAGC

GATTCCTGG C

ATTCCTGGAGC

GATTCCT G GC

ATTCCTGGAGC

GATTCCTGGC

Less times of opening gaps

Less mismatch

Longer aligned elements

14 of 60

SCORING SYSTEM

  • Match: +1
  • Mismatch: -2
  • Gap: -1

Score: 8x1+3x(-1)+1x(-2)=3

ATTCGTGGAGC

GATTCCTGG C

  • Gap open: -2

Score: 8x1+2x(-1)+1x(-2)+1x(-2)=2

15 of 60

16 of 60

PROTEIN SEQUENCE

  • Chemical and physical properties
  • Sequence conservation

17 of 60

18 of 60

BLOSUM 62

19 of 60

DNA/RNA SEQUENCE ALIGN TO PROTEIN

  • 6 open reading frames
  • Strand specific

20 of 60

GLOBAL ALIGNMENT

  • End to end alignment
  • Input sequences are similar
  • Input sequences have equal size
  • Specie or sample Classification

21 of 60

LOCAL ALIGNMENT

  • Subsequence to subsequence alignment
  • Dissimilar sequences
  • Conserved region discovery
  • Motif searching

22 of 60

LOCAL ALIGNMENT

  • Beware about the aligned length, score and e-value

ATGTTCGACCCTAGTCCCACCAAAGTCGATATAGGAGTGAAAACCACAGGGTGA

AGTCC

23 of 60

24 of 60

EXERCISE

  • I want to check a new subtype of COVID 19
  • GeneA is a regulator in mouse, I want to know is it also exists in human.

25 of 60

PAIRWISE SEQUENCE ALIGNMENT

  • Two by two alignment
  • A query sequence for a searching in a database
  • Mapping of NGS sequencing

26 of 60

MULTIPLE SEQUENCE ALIGNMENT

  • Perform an alignment for more than two sequences
  • Searching conserved regions
  • Checking regulators cross different samples
  • Understanding phylogenetics

27 of 60

28 of 60

FUNCTIONAL REGION SEARCHING

29 of 60

COVID-19 ELL MOTIF

30 of 60

PHYLOGENETIC TREE

31 of 60

EPIDEMIOLOGY

32 of 60

FASTA FILE FORMAT

33 of 60

E-VALUE AND SCORE

  • The Expect value (E) is a parameter that describes the number of hits one can "expect" to see by chance when searching a database of a particular size.
  • E-value decreases exponentially as the Score (S) of the match increases. Essentially, the E value describes the random background noise. For example, an E value of 1 assigned to a hit can be interpreted as meaning that in a database of the current size one might expect to see 1 match with a similar score simply by chance.

34 of 60

E-VALUE AND SCORE

  • The lower the E-value, or the closer it is to zero, the more "significant" the match is.
  • However, virtually identical short alignments have relatively high E values. This is because the calculation of the E value takes into account the length of the query sequence.
  • The Expect value can also be used as a convenient way to create a significance threshold for reporting results. You can change the Expect value threshold on most BLAST search pages. When the Expect value is increased from the default value of 10, a larger list with more low-scoring hits can be reported.

35 of 60

Cutoff

Descriptions

E-value < 10e-100

Identical sequences. You will get long alignments across the entire query and hit sequence.

10e-100 < E-value < 10e-50

Almost identical sequences. A long stretch of the query protein is matched to the database.

10e-50 < E-value < 10e-10 

Closely related sequences, could be a domain match or similar.

10e-10 < E-value < 1

Could be a true homologue but it is a gray area.

E-value > 1 

Proteins are most likely not related

E-value > 10

Hits are most likely junk unless the query sequence is very short.

36 of 60

SIMILARITY, IDENTITY AND HOMOLOGY

  • Similarity
    • The nucleotides or amino acids of the sequences are related. In BLAST, the similarity refers to a matrix of score.
  • Identity
    • The nucleotides or amino acids of the sequences are identical.

37 of 60

38 of 60

HOMOLOGY

  • Homology in bioinformatics refers to the biological homology between DNA, RNA and protein sequences which are defined in terms of shared ancestral properties in the evolutionary tree of life. In other words, it is the common evolutionary ancestry of two sequences.

39 of 60

THE DIFFERENCE BETWEEN HOMOLOGY AND SIMILARITY

  • Homology refers to a statement about common evolutionary ancestry of two sequences while similarity refers to the degree of likeness between two sequences. So, this is the key difference between homology and similarity in bioinformatics.
  • In addition, homology cannot be calculated since it could be true or false and usually depend on the hypothesis while similarity can be easily calculated as a percentage of similar residues over a given length of the alignment. Hence, this is a significant difference between homology and similarity in bioinformatics.

40 of 60

HOMOLOGY, ORTHOLOGY AND PARALOGY

  • Homology
    • The sequences from a common evolutionary ancestry.
  • Orthology
    • The pairs of genes that started diverging via evolutionary speciation
  • Paralogy
    • The pairs of genes that started diverging via gene duplication

41 of 60

BLAST

https://blast.ncbi.nlm.nih.gov/Blast.cgi

42 of 60

BLAST

43 of 60

BLAST

44 of 60

BLAST

45 of 60

BLAST

46 of 60

BLAST

47 of 60

BLAST

48 of 60

EMBOSS NEEDLE

https://www.ebi.ac.uk/Tools/psa/emboss_needle/

49 of 60

EMBOSS NEEDLE

50 of 60

CLUSTALW

https://www.genome.jp/tools-bin/clustalw

51 of 60

CLUSTALW

52 of 60

T-COFFEE

http://tcoffee.crg.cat/apps/tcoffee/index.html

53 of 60

T-COFFEE

54 of 60

T-COFFEE

55 of 60

MUSCLE

https://www.ebi.ac.uk/Tools/msa/muscle/

56 of 60

MUSCLE

57 of 60

PHYLOGENY

https://www.ebi.ac.uk/Tools/phylogeny/simple_phylogeny/

58 of 60

PHYLOGENY

59 of 60

MEME

https://meme-suite.org/meme/tools/meme

60 of 60

MEME