Multi-Relief implementation of distance measure(s)

From Master Projects
Jump to: navigation, search


Multi-Relief implementation of distance measure(s)
status: finished
Master: project within::Bioinformatics
Student name: student name::Sudesh Jethoe
Dates
Start start date:=2009/04/01
End end date:=2009/05/31
Supervision
Supervisor: Anton Feenstra
Poster: has poster::Media:Verslag_bacheloropdracht_Sudesh_Jethoe.pdf

Signature supervisor



..................................

Abstract

Uitwerken en/of implementeren van verschillende afstandsmaten in Multi-Relief, in plaats van de nu gebruikte Hamming-distance. Voor zowel nearest-hit/nearest-miss detectie, als voor het bepalen van de gewichts-vector wordt nu de Hamming-afstand (scalair of vectoriëel) tussen de sequenties gebruikt. Verwacht wordt dat gebruik van substitutie-scores (b.v. uit de BLOSUM matrix) betere voorspellingen op zal leveren. Resultaten worden gevalideerd aan de hand van bekende sites in een 7-tal eiwitfamilies, waaronder LacI, GPCR, Ras en Smad.


Inleiding

Het RELIEF algoritme is een methode om te voorspellen waar eiwitfamilies, sites hebben, die bepalend zijn voor hun specifieke activiteit. Dit wordt gedaan door het scoren van de onderdelen (aminozuren) van eiwitten op mogelijke specifieke functionele activiteit, hierbij krijgen onderdelen van het eiwit die waarschijnlijk nodig zijn voor de specifieke werking van het eiwit een hoge score en onderdelen van het eiwit die waarschijnlijk geen of geen specifieke -functie hebben een lage score. Deze score wordt in eerste instantie berekend aan de hand van het RELIEF algoritme. Dit algoritme vergelijkt twee klassen (bestaande uit uitgelijnde sequenties) van eiwitsequenties en bepaalt hiervoor hoever zij uit elkaar liggen. Deze bepaling wordt gedaan door eerst binnen 1 klasse 2 eiwitsequenties te vergelijken (bijv sequentie A en B) en hiervan de Hamming distance te bepalen. Hierna word de Hamming distance bepaald tussen 2 klasses, gebruikmakende van de vorige klasse. Dan worden bijvoorbeeld de afstand bepaald tussen sequentie A uit klasse 1 en sequentie C uit klasse 2. Het verschil AC-AB (als vector of som) is dan de RELIEF score.

Multi-RELIEF houdt ook rekening met ontstane mutaties in sequenties als gevolg van afstamming. Dit doet door niet twee, maar meerdere klassen, met elkaar te vergelijken. De multi-RELIEF methode kan ook rekening houden met de 3D-structuur, hiervoor word gebruik gemaakt van lijsten met bekende 3d-informatie van de te bepalen sequenties. Sites die dicht bij elkaar liggen krijgen aan de hand hiervan, na bepaling van de RELIEF score, bonuspunten.


Opdracht

De opdracht is om het multi-RELIEF algoritme aan te passen. Dit op zo een manier dat deze tijdens het vergelijken ook rekening houdt met de waarschijnlijkheid dat aminozuren op sites vervangen zijn door andere aminozuren of juist hetzelfde zijn gebleven. In plaats van een verschil van 1, 0 of -1 kan er dan per site dan een verfijndere score uitkomen, welke tot betere resultaten zou kunnen leiden.


Bronnen

Marchiori, E.*, Pirovano, W., Heringa, J. and Feenstra, K.A.* (2006) A Feature Selection Algorithm for Detecting Subtype Specific Sites for Smad Receptor Binding, Bio-ICMLA06 (IEEE), 168-173.

Ye, K., Feenstra, K.A, Heringa, J., IJzerman, A.P. and Marchiori, E. (2008). Multi-RELIEF: a method to recognize specificity determining residues from multiple sequence alignments using a Machine Learning approach for feature weighting, Bioinformatics, 24(1): 18-25.

www.ibi.vu.nl/programs/multirelief/