Markov lánc Monte Carlo módszerek a bioinformatikában
Title in English
MCMC methods in bioinformatics
Keywords in Hungarian
Markov chain Monte Carlo, bioinformatics, algorithms, alignments, genome rearrangement
Keywords in English
Markov lánc Monte Carlo, bioinformatika, algoritmusok, szekvenciaillesztés, genomátrendezőséds
Discipline
Bioinformatics (Council of Medical and Biological Sciences)
60 %
Mathematics (Council of Physical Sciences)
40 %
Ortelius classification: Applied mathematics
Panel
Genetics, Genomics, Bioinformatics and Systems Biology
Department or equivalent
Alfréd Rényi Institute of Mathematics
Starting date
2011-01-01
Closing date
2013-12-31
Funding (in million HUF)
13.983
FTE (full time equivalent)
2.40
state
closed project
Summary in Hungarian
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.
Summary
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.
Final report
Results in Hungarian
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.
Results in English
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.
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
