Transcript Bionformatics 2

Algorithms in Bioinformatics
Dipl. Ing. (FH) Patrick Grossmann
[email protected]
Contents
•
•
•
•
Bioinformatics short repetition
Used algorithms
Example on genetic algorithm
Conclusion
2
Short repetition
• Homology modeling
Discover unknown
sequences
Create model
with known
sequences
20
Short repetion
• MOST important part of disease research
– If you can’t fold it, you can’t use it
Examples for needing of algorithms
• Calculations
• Proof of theoretical knowledge
• Research
–
–
–
–
Cancer
Disease
Drugs
Agriculture
Some used Algorithms
•
•
•
•
Evolution Strategies
Genetic programming
Ant colony optimizing
Evolutionary Alogrithms
– Genetic Algorithm (GA)
Evolution strategies
• Only used for numerical optimizations
• Can not be used for:
– Systems which can not be describe in
equations
– Systems which have to be approximated
Genetic programming (GP)
• Possibility to create complex programs
• Can learn by itself how to solve the task
• Recursive, Tree structure
Source: http://www.genetic-programming.com/evolveV2DF2003621.GIF
GP – easy example
• Easy example:
Source: http://geneticprogramming.us/Genetic_Operations.html
GP - Real life example
Ant colony optimization
• Solving Schedulingproblems
Genetic algorithm (GA)
• Inspired by evolution
• Powerful for Optimizing of folding
– Protein structure forecast
– Molecular biology
• 1 Chromosome = 1 Bit (Memory, Speed!)
• No MMU needed -> Embedded systems!
• Limited amount of operators (binary only)
Genetic algorithm - procedure
1 Encode Gen to binary values
2 Generate Generation Zero
3 Create weights for each Individual
Algorithm starts here
4 Pair two parents
5 Create children
6 Check mutation probabilty
Genetic algorithm - Attributes
• Algorithm :
depends on task
• Coding:
Grey code -> Hamming Distance!
• Starting population:
• Weight:
depends on task
e.g fertility probability
• Choosing:
Roulette, SUS
• Crossing:
One-Point, N-Point ...-Crossover
GA Example – Step 1 to 3
•Algorithm given as:
•Coding: 5 Bit length,
•Starting population: 4 inviduals
•Weight: invidually specified
•Selection probability Ps is given by:
GA Example – Step 4
• Using roulette method
– 1,2 and 3,4 are paired
• Crossing method: One-Point-Crossover
(given with random seeds)
– 1,2 are cut at 4th part
– 3,4 are cut at 2nd part
GA Example – Step 5
• Children generated
• Different values
• Now lets mutate the Chromosomes
GA Example – Step 6
• Mutation:
• Low probability, lets say: Pm= 1/100
• Now lets calculate: 20 bits x 1/100 = 0.2
• No mutation in this example, due to low
probability
• Mutation == inverting a bit
Genetic Algorithm (GA) - Results
• Average Value increased:
– 293 to 439 -> 961 should be achieved
• Repeat - back to Step 4
Conclusion
•
•
•
•
There are different algorithms
Each algorithm has its advantages
It is up to the user to choose the right one
The given example is based on the book
Computational Intelligence (Teubner Vieweg )
26
That’s it that’s all
27
Source: http://thumbs.dreamstime.com/z/dna-strand-question-mark-against-arranged-used-as-illustrations-medical-health-40876052.jpg