Finite Automata - NFA and DFA

 

Finite Automata - is the simplest machine to recognize patterns.

A finite Automata consists of :

   Q : Finite set of states.

Σ : Set of Input Symbols.

q : Initial State

F : Set of Final States

δ : Transition Function

Formal specification of machine is {Q, Σ, q, F, δ}

FA is characterized into two types:

Deterministic Finite Automata(DFA)

Non Deterministic Finite Automata(NFA)

Deterministic Finite Automata

DFA consists of 5 tuples {Q, Σ, q, F, δ}. 

Q : set of all states.
Σ : set of input symbols. ( Symbols which machine takes as input )
q : Initial state. ( Starting state of a machine )
F : set of final state.
δ : Transition Function, defined as δ : Q X Σ --> Q.

In DFA, when an input character is given the machine goes to one state only.
A transition function is defined on every state for every input symbol.

ALso in DFA null (or ε) move is not allowed.

 i.e., DFA cannot change state without any input character.

For example, below DFA with Σ = {0, 1} accepts all strings ending with 0

2) Nondeterministic Finite Automata(NFA)

NFA is similar to DFA except following additional features:
1. Null (or ε) move is allowed i.e., it can move forward without reading symbols.
2. Ability to transmit to any number of states for a particular input.

Due to above additional features, NFA has a different transition function, rest is same as DFA.
δ: Transition Function
δ:  Q X (Σ U ε ) --> 2 ^ Q. 
As you can see in transition function is for any input including null (or ε), NFA can go to any state number of states.

Some Important Points:
1. Every DFA is NFA but not vice versa.
Justification:
Since all the tuples in DFA and NFA are the same except for one of the tuples, which is Transition Function (δ)
In case of DFA
δ : Q X Σ --> Q
In case of NFA
δ : Q X Σ --> 2Q
Now if you observe you’ll find out Q X Σ –> Q is part of Q X Σ –> 2Q.

In the RHS side, Q is the subset of 2Q which indicates Q is contained in 2Q or Q is a part of 2Q, however, the reverse isn’t true. So mathematically, we can conclude that every DFA is NFA but not vice-versa. Yet there is a way to convert an NFA to DFA, so there exists an equivalent DFA for every NFA.
2. Both NFA and DFA have same power and each NFA can be translated into a DFA.
3. There can be multiple final states in both DFA and NFA.
4. NFA is more of a theoretical concept.
5. DFA is used in Lexical Analysis in Compiler.

Different types of scoring matrix

 We know how to calculate scoring matrix. There are different types of scoring matrix based on the concept of frequency of occuring of certain amino acids within the biological sequences, there are multiple strategies to compute this frequencies. Towards that we are going discuss about PAM Scoring Matrix.

The alignments are scored very nicely if we use an empirical scoring method. That is a scoring matrix based on experimental observed frequencies of amino acids, there are multiple types of matrix but the main matrices are PAM and BLOSSUM matrix.

So first we will discuss about PAM Scoring Matrix

PAM - Point Accepted Mutations Matrix.

Point accepted Mutation Matrix is a substitution of one amino acid by another such that the protein stays conserved.

Note: There are cases where the substitution of one amino acid by another amino acid changes protien, but in PAM those mutations(substitutions) are considered where the overall function of the protein stay conserved or stays the same.

PAM Unit:

PAM unit is the time in which 1% of amino acids in a sequence undergo accepted mutations and this will be PAM1.

Since sequences are long and there are a multiple neucliotides or amino acids in the sequences, then 1% of sequences changed does not necessarily mean that a 100% PAM will have 100% variation in the sequences, because the same site can be changed more than one time, ie. if the same site mutated multiple times then the entire sequence may not be changed for the entire protien.

To understand this we will consider a graph, in which the sequence difference and PAM Distance are compared

Figure 1:

In this a PAM Distance of 100 dosen't mean that there is 100 percentage change in the sequence, because one site on mutation will further mutate and will be accumulated with multiple mutations.

So the experimental data shows if you have a 100 PAM Distance then only 55 to 60 percentage of the sites in the protein are actually mutated. So for the 85 % variations the PAM Distance will increase over than 300.

figure 2

In figure 2 the value of k is 20 (ie 20 amino acids) you can calculate the PAM 1 by using this calculation.

If you want to find PAM 2 then just square the PAM1

similarly if you want to find PAM'n' then multiply PAM 1 'n' times.

If you multiply PAM 1 by 250 times then PAM 250 matrix will get the subsitution matrix like this

In conclusion PAM Matrixes are scoring matrixes that are used for comparing sequences. We can compute PAM 1, PAM2 etc upto PAM 250 or more and PAM 120 is considered as optimal scoring matrix

Deriving Scoring Matrix

 We know the importances of Scoring Matrixes, Instead of scoring the same score for all matches or mismatches the scoring matrix allow us to have a flexible scoring scheme. Flexible scoring scheme means substitution of specific amino acids by others is scored differently and similarly for matches and mismatches all of the scores are computed based on the frequency of occurance of these amino acids in similar protein sequnces.

How do we arrive the Scoring Matrix?

We compare biological sequences by aligning them or we call it as Pair wise sequence alignment, and during this alignment we rank the matches between sequences using scoring matrix

By looking at the chemical properties of amino acids we can see which amino acid will ge higher score

and which amino acid substitution get a lower score.

In the above figure 20 amino acids are listed and colorful diagram shows the chemicalproperties as well.

For example,the green ones are the polar amino acids the brown ones as indicated are the charged amino acids, there are lots of hydrophobhic amino acids, hydroxilix amino acids, tiny amino acids( basically very small amino acids), small amino acids, acidic amino acids and basic amino acids. These are the different properties of amino acids that make them get substituted or conserved within the protein sequences

Figure2

Now let's consider the report generated by Robinson and Robinson several years ago.

In this the columns states that each amino acid has a specific frequency of occurance on average, that means Alanin has an average occurance of 0.078 on a scale of 1 similarly Argenine etc.

Now let's discuss how did they compute frequency, for that similar protein sequences was considered and counted the occurance of each amino acid an normalised it between zero and one.

Example: 

Consider the case of three amino acids from the 20 amino acids inorder to simplify the problem. And also consider a small protein comprising of 4 amino acids.

Next count how many A's are converted into A, how many A's are converted into B's, how many A's are converted into C's,how many B's are converted into B's, how many B's are converted into C's, and how many C's are converted into C's

The observed frequencies  fij in fig.5 shows the frequencies of ocuurance in the conversion, there are total 60 conversion and if you consider C to C then it is 2/60

fig.6

The C in sequence no.3 is converted to another C in sequence 5 likewise the C in sequence no.2 is converted to another C in sequence no.3 thus it got the count as 2 out of 60. 

If we consider B to B then 6 B's are converted to other B's  then we will get 6 over 60.

figure 7

Likewise others are also calculated.

Here fij denotes the conversion of one amino acid to another

figure 8

In fig.8 we can the observed frequencies fi which will be the observed frequencies of the entire set of proteins, ie the frequencies of each amino acids. If we consider the case of C the value 4 over 24 means the entire C in the particular sequence.

figure 9

Now considering

Here S(i,j) means for Scoring matrix any entry can be computed for example i, j by computing log to the second base of fij over pij's. So pij means the frequency of occurance of amino acids if they are the same ie pij = fifi if i equals to j , if they are different means i is not equal to j then pij equals to 2 times fi and fj.

Likewise pij is computed . 

And you can see 2sij is also computed 

And finally scoring matrix is obtained .

We can see in scoring matrix each element is an integer, so all elements in Sij into integers.

Finally the Scoring Matrix for the 3 amino acids is obtained.

In conclusion based on the frequency of certain amino acids we can compute the scoring matrix and then we can use them to compare sequences that are given for comparisons

Scoring Matrix in Bioinformatics

In Pairwise Sequence Alignment or comparison of two sequences as a pair is essentialy to compare their constitution. The constitution can be from amino acis or neucliotides. When  You want to compare these two sequences then you want to score the result.But in the reallife due to the evolutionary pressures the rate of replacing the different amino acid by others is different.So therefore it is necessary to incorporate the variable propencity of replacement or substitution by suitable scores.In this goal we are helped by Scoring Matrix.

We will see what are the scoring matrixes, how we will build scoring matrixes and how we can use them in the alignment process.

Introduction of Scoring Matrix

 

An amino acid can be replaced by another amino acid based on their chemical ,physical and other special properties. so if two amino acids have same chemical behaviour then there is a high chance for their substitution during evolution, However if there is totaly different properties then there is  very low chance of such an amino acid replaced by another amino acid

So the scoring Matrixes they are variable or flexible in scoring such substitions and therefore they have the substition for each amino acid scored differently, ie scoring matrixes have substitution value of each amino acid in a unique way.

How to build Scoring Matrix?

Consider the protein sequences that are there in nature, find protein sequences that are similar to each other and homologous to each other, so once we isolated the set of similar protein sequences then we see which amino acid in one sequence is substituted with which amino acid in the other sequences.In this way we build a frequency list of amino acid that is frequently an amino acid is substituted by another amino acid,

Scores in the Scoring Matrix

So the scoring Matrix by looking at such frequencies may contain a +ve value ie a very easy transition or substitution from one amino acid to another , -ve value which means a rare substitution and may be a zero  as well.

Here is an example of a protein called Ubiquitin

List of ubiqutins are shown from humans, chimps, mouse etc. and their sequences have been aligned with each other as we can see some of the amino acids are raely substituted while some others are completely conserved while some other amino acids are changed.

So what we do in such a frequency count is to apply a formula

Here S will be the Scoring Matrix

         a  will be he first amino acid

         b  will be the second amino acid

So subtitution a by b will be scored by multiplying some constants

 by the log of this ratio 

Pab is the probability of amino acid 'a' substituted by amino 'b' where a nd b can be any two amino acids.

fa and fb  is the frequencies of amino acids a and b

So by computing the S for a,b, and if you vary a and b to all the amino acids that is 20 amino acids you can arrive at the scoring matrix.

Let us consider a scoring matrix

Consider the negative score -5 when D is substituted by W or zeros when S is substitued by D Q G. The diagonal indicated by red line shows very high scores specially if C is substituted by another C the score is substituted by 13, which means C is mostly conserved.

So in Conclusion, A postive value  like +1,+5 has been assigned for match, similarly -10, -2 for mismatches for all the amino acids the scoring matrixes selectively score or score differently for each amino acids depending on their chemical and physical properties which are reflected in their frequency of occurance.

Static and Dynamic Scoping

The scope of a variable x is the region of the program in which uses of x refers to its declaration. One of the basic reasons of scoping is to keep variables in different parts of program distinct from one another.

Scoping is generally divided into two classes:
1.Static Scoping
2.Dynamic Scoping

Static Scoping:

Static scoping is also called lexical scoping. In this scoping a variable always refers to its top level environment. This is a property of the program text and unrelated to the run time call stack. Static scoping also makes it much easier to make a modular code as programmer can figure out the scope just by looking at the code. In contrast, dynamic scope requires the programmer to anticipate all possible dynamic contexts.

Dynamic Scoping:

With dynamic scope, a global identifier refers to the identifier associated with the most recent environment, and is uncommon in modern languages. In technical terms, this means that each identifier has a global stack of bindings and the occurrence of a identifier is searched in the most recent binding.

A perl code to demonstrate dynamic scoping

$x = 10;

sub f 

{ 

   return $x; 

}

sub g 

{ 

   # Since local is used, x uses

   # dynamic scoping. 

   local $x = 20; 

  

   return f(); 

}

print g()."\n";

Static Vs Dynamic Scoping

In most of the programming languages static scoping is dominant. This is simply because in static scoping it’s easy to reason about and understand just by looking at code. We can see what variables are in the scope just by looking at the text in the editor.

Dynamic scoping does not care how the code is written, but instead how it executes. Each time a new function is executed, a new scope is pushed onto the stack.

Perl supports both dynamic and static scoping. 

DBMS Normalization : 1NF, 2NF, 3NF, BCNF

Normalization of Database

Database Normalization is a technique of organizing the data in the database.

Normalization is a systematic approach of decomposing tables to eliminate

data redundancy (repetition) and undesirable characteristics like Insertion, Update

and Deletion Anomalies.

It is a multi-step process that puts data into tabular form, removing duplicated data

from the relation tables.

Normalization is used for mainly two purposes,

• Eliminating redundant (useless) data.
• Ensuring data dependencies make sense i.e data is logically stored.

Problems Without Normalization

If a table is not properly normalized and have data redundancy then it will take a lots

of memory space and also it will be difficult to handle and update the database,

without facing data loss. Insertion, Updation and Deletion Anomalies are very frequent if

database is not normalized.

Let's consider an example of a Student table.

rollno	name	branch	hod	office_tel
401	Akon	CSE	Mr. X	53337
402	Bkon	CSE	Mr. X	53337
403	Ckon	CSE	Mr. X	53337
404	Dkon	CSE	Mr. X	53337

In the table above, we have data of 4 Computer Sci. students. As we can see, data

for the fields branch, hod(Head of Department) and office_tel is repeated for the students

who are in the same branch in the college, this is Data Redundancy.

---

Insertion Anomaly

Suppose for a new admission, until and unless a student opts for a branch, data of the

student cannot be inserted, or else we will have to set the branch information as NULL.

Also, if we have to insert data of 100 students of same branch, then the branch information

will be repeated for all those 100 students.

These scenarios are nothing but Insertion anomalies.

---

Updation Anomaly

What if Mr. X leaves the college? or is no longer the HOD of computer science department?

In that case all the student records will have to be updated, and if by mistake we miss

any record, it will lead to data inconsistency. This is Updation anomaly.

---

Deletion Anomaly

In our Student table, two different informations are kept together, Student information and

Branch information. Hence, at the end of the academic year, if student records are deleted,

we will also lose the branch information. This is Deletion anomaly.

---

Normalization Rule

Normalization rules are divided into the following normal forms:

• First Normal Form
• Second Normal Form
• Third Normal Form
• BCNF
• Fourth Normal Form

---

First Normal Form (1NF)

For a table to be in the First Normal Form, it should follow the following 4 rules:

1. It should only have single(atomic) valued attributes/columns.
2. Values stored in a column should be of the same domain
3. All the columns in a table should have unique names.
4. And the order in which data is stored, does not matter.

Second Normal Form (2NF)

For a table to be in the Second Normal Form,

1. It should be in the First Normal form.
2. And, it should not have Partial Dependency.

---

Third Normal Form (3NF)

A table is said to be in the Third Normal Form when,

1. It is in the Second Normal form.
2. And, it doesn't have Transitive Dependency.

Boyce and Codd Normal Form (BCNF)

Boyce and Codd Normal Form is a higher version of the Third Normal form.

This form deals with certain type of anomaly that is not handled by 3NF. A 3NF table which

does not have multiple overlapping candidate keys is said to be in BCNF.

For a table to be in BCNF, following conditions must be satisfied:

• R must be in 3rd Normal Form
• and, for each functional dependency ( X → Y ), X should be a super Key.

Rules for First Normal Form

The first normal form expects you to follow a few simple rules while designing your database,

and they are:

Rule 1: Single Valued Attributes

Each column of your table should be single valued which means they should not contain

multiple values. We will explain this with help of an example later, let's see the other rules

for now.

---

Rule 2: Attribute Domain should not change

This is more of a "Common Sense" rule. In each column the values stored must be of the

same kind or type.

For example: If you have a column dob to save date of births of a set of people, then you

cannot or you must not save 'names' of some of them in that column along with 'date of birth'

of others in that column. It should hold only 'date of birth' for all the records/rows.

---

Rule 3: Unique name for Attributes/Columns

This rule expects that each column in a table should have a unique name. This is to avoid

confusion at the time of retrieving data or performing any other operation on the stored data.

Example

roll_no	name	subject
101	Akon	OS, CN
103	Ckon	Java
102	Bkon	C, C++

Our table already satisfies 3 rules out of the 4 rules, as all our column names are unique,

we have stored data in the order we wanted to and we have not inter-mixed different type

of data in columns.

But out of the 3 different students in our table, 2 have opted for more than 1 subject.

And we have stored the subject names in a single column. But as per the 1st Normal form

each column must contain atomic value.

How to solve this Problem?

It's very simple, because all we have to do is break the values into atomic values.

Here is our updated table and it now satisfies the First Normal Form.

roll_no	name	subject
101	Akon	OS
101	Akon	CN
103	Ckon	Java
102	Bkon	C
102	Bkon	C++

By doing so, although a few values are getting repeated but values for the subject column are

now atomic for each record/row.

Using the First Normal Form, data redundancy increases, as there will be many columns with

same data in multiple rows but each row as a whole will be unique.

What is Second Normal Form?

For a table to be in the Second Normal Form, it must satisfy two conditions:

1. The table should be in the First Normal Form.
2. There should be no Partial Dependency.

What is Partial Dependency? Do not worry about it. First let's understand what is

Dependency in a table?

---

What is Dependency?

Let's take an example of a Student table with columns student_id, name, reg_no(registration number), branch and address(student's home address).

student_id	name	reg_no	branch	address

In this table, student_id is the primary key and will be unique for every row, hence we can

use student_id to fetch any row of data from this table

Even for a case, where student names are same, if we know the student_id we can easily

fetch the correct record.

student_id	name	reg_no	branch	address
10	Akon	07-WY	CSE	Kerala
11	Akon	08-WY	IT	Gujarat

Hence we can say a Primary Key for a table is the column or a group of columns(composite

key) which can uniquely identify each record in the table.

I can ask from branch name of student with student_id 10, and I can get it. Similarly, if I ask for name of student with student_id 10 or 11, I will get it. So all I need is student_id and every other column depends on it, or can be fetched using it.

This is Dependency and we also call it Functional Dependency.

---

What is Partial Dependency?

Now that we know what dependency is, we are in a better state to understand what partial

dependency is.

For a simple table like Student, a single column like student_id can uniquely identfy all the records in a table.

But this is not true all the time. So now let's extend our example to see if more than 1 column together can act as a primary key.

Let's create another table for Subject, which will have subject_id and subject_name fields and subject_id will be the primary key.

subject_id	subject_name
1	Java
2	C++
3	Php

Now we have a Student table with student information and another table Subject for storing

subject information.

Let's create another table Score, to store the marks obtained by students in the respective

subjects. We will also be saving name of the teacher who teaches that subject along with

marks.

score_id	student_id	subject_id	marks	teacher
1	10	1	70	Java Teacher
2	10	2	75	C++ Teacher
3	11	1	80	Java Teacher

In the score table we are saving the student_id to know which student's marks are these and

subject_id to know for which subject the marks are for.

Together, student_id + subject_id forms a Candidate Key for this table, which can be the Primary key.

How this combination can be a primary key?

See, if I ask you to get me marks of student with student_id 10, can you get it from this table? No, because you don't know for which subject. And if I give you subject_id, you would not know for which student. Hence we need student_id + subject_id to uniquely identify any row.

But where is Partial Dependency?

Now in the Score table, we have a column names teacher which is only dependent on the subject, for Java it's Java Teacher and for C++ it's C++ Teacher & so on.

Now as we just discussed that the primary key for this table is a composition of two columns which is student_id & subject_id but the teacher's name only depends on subject, hence the subject_id, and has nothing to do with student_id.

This is Partial Dependency, where an attribute in a table depends on only a part of the primary key and not on the whole key.

---

How to remove Partial Dependency?

There can be many different solutions for this, but out objective is to remove teacher's name

from Score table.

The simplest solution is to remove columns teacher from Score table and add it to the Subject table. Hence, the Subject table will become:

subject_id	subject_name	teacher
1	Java	Java Teacher
2	C++	C++ Teacher
3	Php	Php Teacher

And our Score table is now in the second normal form, with no partial dependency.

score_id	student_id	subject_id	marks
1	10	1	70
2	10	2	75
3	11	1	80

---

Quick Recap

For a table to be in the Second Normal form, it should be in the First Normal form and it should

not have Partial Dependency.

Partial Dependency exists, when for a composite primary key, any attribute in the

table depends only on a part of the primary key and not on the complete primary key.

To remove Partial dependency, we can divide the table, remove the attribute which

is causing partial dependency, and move it to some other table where it fits in well.

Third Normal Form (3NF)

Student Table

student_id	name	reg_no	branch	address
10	Akon	07-WY	CSE	Kerala
11	Akon	08-WY	IT	Gujarat
12	Bkon	09-WY	IT	Rajasthan

Subject Table

subject_id	subject_name	teacher
1	Java	Java Teacher
2	C++	C++ Teacher
3	Php	Php Teacher

Score Table

score_id	student_id	subject_id	marks
1	10	1	70
2	10	2	75
3	11	1	80

In the Score table, we need to store some more information, which is the exam name and total

marks, so let's add 2 more columns to the Score table.

score_id	student_id	subject_id	marks	exam_name	total_marks

---

Requirements for Third Normal Form

For a table to be in the third normal form,

1. It should be in the Second Normal form.
2. And it should not have Transitive Dependency.

---

What is Transitive Dependency?

With exam_name and total_marks added to our Score table, it saves more data now. Primary key for our Score table is a composite key, which means it's made up of two attributes or columns → student_id + subject_id.

Our new column exam_name depends on both student and subject. For example, a mechanical engineering student will have Workshop exam but a computer science student won't. And for some subjects you have Prctical exams and for some you don't. So we can say that exam_name is dependent on both student_id and subject_id.

And what about our second new column total_marks? Does it depend on our Score table's primary key?

Well, the column total_marks depends on exam_name as with exam type the total score changes. For example, practicals are of less marks while theory exams are of more marks.

But, exam_name is just another column in the score table. It is not a primary key or even a part of the primary key, and total_marks depends on it.

This is Transitive Dependency. When a non-prime attribute depends on other non-prime attributes rather than depending upon the prime attributes or primary key.

---

How to remove Transitive Dependency?

Again the solution is very simple. Take out the columns exam_name and total_marks from Score

table and put them in an Exam table and use the exam_id wherever required.

Score Table: In 3rd Normal Form

score_id	student_id	subject_id	marks	exam_id

The new Exam table

exam_id	exam_name	total_marks
1	Workshop	200
2	Mains	70
3	Practicals	30

---

Advantage of removing Transitive Dependency

The advantage of removing transitive dependency is,

• Amount of data duplication is reduced.
• Data integrity achieved.

Boyce-Codd Normal Form (BCNF)

Rules for BCNF

For a table to satisfy the Boyce-Codd Normal Form, it should satisfy the following two

conditions:

1. It should be in the Third Normal Form.
2. And, for any dependency A → B, A should be a super key.

The second point sounds a bit tricky, right? In simple words, it means, that for a

dependency A → B, A cannot be a non-prime attribute, if B is a prime attribute.

---

Time for an Example

Below we have a college enrolment table with columns student_id, subject and professor.

student_id	subject	professor
101	Java	P.Java
101	C++	P.Cpp
102	Java	P.Java2
103	C#	P.Chash
104	Java	P.Java

As you can see, we have also added some sample data to the table.

In the table above:

• One student can enrol for multiple subjects. For example, student with student_id 101, has opted for subjects - Java & C++
• For each subject, a professor is assigned to the student.
• And, there can be multiple professors teaching one subject like we have for Java.

What do you think should be the Primary Key?

Well, in the table above student_id, subject together form the primary key, because using

student_id and subject, we can find all the columns of the table.

One more important point to note here is, one professor teaches only one subject, but one

subject may have two different professors.

Hence, there is a dependency between subject and professor here, where subject depends

on the professor name.

This table satisfies the 1st Normal form because all the values are atomic, column names

are unique and all the values stored in a particular column are of same domain.

This table also satisfies the 2nd Normal Form as their is no Partial Dependency.

And, there is no Transitive Dependency, hence the table also satisfies the 3rd Normal Form.

But this table is not in Boyce-Codd Normal Form.

---

Why this table is not in BCNF?

In the table above, student_id, subject form primary key, which means subject column

is a prime attribute.

But, there is one more dependency, professor → subject.

And while subject is a prime attribute, professor is a non-prime attribute, which is not

allowed by BCNF.

---

How to satisfy BCNF?

To make this relation(table) satisfy BCNF, we will decompose this table into two tables,

student table and professor table.

Below we have the structure for both the tables.

Student Table

student_id	p_id
101	1
101	2
and so on...

And, Professor Table

p_id	professor	subject
1	P.Java	Java
2	P.Cpp	C++
and so on...

And now, this relation satisfy Boyce-Codd Normal Form. Next we will learn

about the Fourth Normal Form.

---

A more Generic Explanation

In the picture below, we have tried to explain BCNF in terms of relations.