Markov lánc Monte Carlo módszerek a bioinformatikában  részletek

súgó  nyomtatás 
vissza »

 

Projekt adatai

 
azonosító
84297
típus PD
Vezető kutató Miklós István
magyar cím Markov lánc Monte Carlo módszerek a bioinformatikában
Angol cím MCMC methods in bioinformatics
magyar kulcsszavak Markov chain Monte Carlo, bioinformatics, algorithms, alignments, genome rearrangement
angol kulcsszavak Markov lánc Monte Carlo, bioinformatika, algoritmusok, szekvenciaillesztés, genomátrendezőséds
megadott besorolás
Bioinformatika (Orvosi és Biológiai Tudományok Kollégiuma)60 %
Matematika (Műszaki és Természettudományok Kollégiuma)40 %
Ortelius tudományág: Alkalmazott matematika
zsűri Genetika, Genomika, Bioinformatika és Rendszerbiológia
Kutatóhely HUN-REN Rényi Alfréd Matematikai Kutatóintézet
projekt kezdete 2011-01-01
projekt vége 2013-12-31
aktuális összeg (MFt) 13.983
FTE (kutatóév egyenérték) 2.40
állapot lezárult projekt
magyar összefoglaló
Kezdetben a pontozás -- távolság és szimilaritás -- alapú optimalitációs módszerek dominálták a bioinformatikai gondolkodást. A kilencvenes évektől kezdődően egy paradigmaváltás történt, és a parszimónia alapú módszereket folyamatosan felváltották a statisztikai módszerek, ahol az optimális és szuboptimális megoldások eloszlását vizsgálták. A paradigmaváltás kezdetén olyan módszereket vizsgáltak, ahol egy teljes eloszlás vizsgálatának a számolásigénye nagyságrendileg megegyezett az optimális megoldást megkereső algoritmus számolásigényével, de ahogy a statisztikai megközelítés elfogadottabbá vált, előtérbe kerültek olyan bonyolult modellek, amelyek közvetlen analitikus vizsgálata már komplikált volt. Ezekre a modellekre az általánosan elterjedt vizsgálati módszer a Markov lánc Monte Carlo (MCMC) technika lett.
A pályázat célkitűzése új, hatékony MCMC technikák kifejlesztése amelyek bioinformatikailag releváns eloszlásokhoz konvergálnak, és lehetőleg annak a matematikai bizonyítása, hogy ezen új metódusok gyorsan konvergálnak a kívánt eloszláshoz. Az elméleti munka mellett a kidolgozott technikák számítógépes implementálásra is kerülnek, és alkalmazhatóságuk demonstrálva lesz bioinformatikai alkalmazásokon keresztül bemutatva, mint például filogenetikai vizsgálatok, protein térszerkezet predikciók, genomátrendeződések vizsgálata, biológiai hálózatok vizsgálata.
angol összefoglaló
From the beginnings till the end of the eighties, score – similarity and distance – based optimization methods dominated the bioinformatics thinking. From the early nineties, bioinformatics research gradually changed focus to statistically rigorous methods, and bioinformaticians got interested in the distribution of optimal and suboptimal solutions. This paradigm change started with computationally feasible models, for which the inferring of the entire distribution has the same order of computational complexity than finding only the optimal solution. As the statistical approach become more accepted, a demand for more involved statistical models emerged. These more sophisticated models were computationally intensive and required new type of inferring methods, in which Markov chain Monte Carlo has been the most widespread.
The objective of this proposal is to develop new MCMC techniques for bioinformatics applications and possibly provide mathematical proofs that the highly sophisticated methods converge quickly to the desired distributions. Above the theoretical research on convergence of MCMC methods, we would like to implement the methods that we developed, and apply it to bioinformatics related problems to demonstrate their power. Such bioinformatical applications will include inferring phylogenies, predicting protein structures, genome rearrangements and biological networks.





 

Zárójelentés

 
kutatási eredmények (magyarul)
Megadtunk egy MCMC metódust, amely vegetáció dinamika paramétereinek Bayesi eloszlását határozza meg. Megmutattuk, hogy pozitív szelekció van a HD motívum fentartására az APP fehérjében. Bebizonyítottuk, hogy a legtakarékosabb DCJ utak polinom időben majdnem egyenletesen mintavételezhetőek és a számuk FPRAS approximálható. Megmutattuk, hogy a swap Markov lánc gyorsan kever félig reguláris fokszámsorozatok realizációin. Hasonlóan, gyorsan kever félig reguláris fokszámsorozatok olyan realizációin, amelyek egy kizárt egyfaktort és csillagot tartalmaznak. Ugyanígy JDM-ek kiegyensúlyozott realizációin is. Képletet adtunk a swap távolságra. Hatékony algoritmust adtunk moduláris string illeszkedésre. Megmutattuk, hogy a legtakarékosabb SCJ scenáriók száma nem approximálható FPRAS módon és nem lehet polinom időben közel egyenletesen mintavételezni őket, hacsak nem RP = NP. Bebizonyítottuk a '4 reverzió sejtést' lineáris gráfokra.
kutatási eredmények (angolul)
We gave an MCMC method to sample the Bayesian distribution of parameters of vegetation dynamics. We showed that there was a positive selection on the HD motifs in APP proteins. We proved that the most parsimonious DCJ scenarios can be almost uniformly sampled in polynomial time and their number can be FPRAS approximated. We proved that the swap Markov chain mixed rapidly on realizations of half-regular degree sequences. Also, it is rapidly mixing on such realizations of half-regular degree sequences that contain a forbidden one-factor and a star-tree. It is also rapidly mixing on the balanced realizations of JDMs. We gave a formula for the swap distance. We gave an efficient algorithm for modulated string searching. We showed that the number of most parsimonious SCJ scenarios cannot be approximated in an FPRAS manner and they cannot be sampled almost uniformly in polynomial time unless RP = NP. We proved the 'four reversal conjecture' for linear graphs.
a zárójelentés teljes szövege https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=84297
döntés eredménye
igen





 

Közleményjegyzék

 
Somodi, I., Miklós, I., Virág, K.: A Bayesian MCMC approach to reconstruct spatial vegetation dynamics from sparse vegetation maps, Landscape Ecology, Volume 26, Number 6, 805-822, 2011
Zádori, Z. Miklós, I.: Positive Evolutionary Selection of an HD Motif on Alzheimer Precursor Protein Orthologues Suggests a Functional Role, PLoS Computational biology, 8(2): e1002356., 2012
Miklos, I.: Sztochasztikus modellek a bioinformatikában, http://www.renyi.hu/~miklosi/SztochasztikusModellek.pdf, 2011
Miklós, I., Tannier, E.: Approximating the number of Double Cut-and-Join scenarios, Theoretical Computer Science 439:30-40, 2012
Péter L. Erdös, Istán Miklós, Lajos Soukup: Towards random uniform sampling of bipartite graphs with given degree sequence, Electronic Journal of Combinatorics, 2013
Erdős, P., Király, Z., Miklós, I.: On the swap-distances of different realizations of a graphical degree sequence, Combinatorics, Probability and Computing / Volume 22 / Issue 03 / May 2013, pp 366-383, 2013
Apostolico, A., Erdős, P.,Miklós, I., Siemons, J: Modulated String Searching, Theoretical Computer Science Available online 14 October 2013, 2013




vissza »