Computational studies in epigenomics using histone modification data THÈSE NO 6327 (2014) PRÉSENTÉE LE 28 AOÛT 2014 À LA FACULTÉ INFORMATIQUE ET COMMUNICATIONS LABORATOIRE DE BIOLOGIE COMPUTATIONNELLE ET BIOINFORMATIQUE PROGRAMME DOCTORAL EN INFORMATIQUE, COMMUNICATIONS ET INFORMATION ÉCOLE POLYTECHNIQUE FÉDÉRALE DE LAUSANNE POUR L'OBTENTION DU GRADE DE DOCTEUR ÈS SCIENCES PAR Nishanth Ulhas NAIR acceptée sur proposition du jury: Prof. E. Telatar, président du jury Prof. B. Moret, Dr Ph. Bucher, directeurs de thèse Prof. S. Hannenhalli, rapporteur Prof. F. Naef, rapporteur Prof. W. Stafford Noble, rapporteur Suisse 2014 —verse32inSriGuruGita(authoredbysageVyasa) Tomywonderfulmotherandfather. Tomybelovedwife. Tomyteachers,advisors,mentors. TothegreatMasters,towhomIcanbuthumblybow. Acknowledgements TosayIhavehadaveryblessedstudentlifewouldbeanunderstatement.Althoughaslongas oneisintheworldofacademicsoneisalwaysastudent,Iunderstandthatwiththecompletion ofmyPhD,Imaynotgetanotheropportunitytobeaformalstudentofscienceandtechnology again.ThereareacountlesspeoplewhoIamdeeplyindebtedtothroughoutmylifewithout whoIwouldnothavesuchawonderfulstudentlife.Iwouldliketothankallofthemandname afewbelow. FirstandforemostIwouldliketothankmyPhDadvisorProf.BernardM.E.Moretformaking meapartoftheLaboratoryofComputationalBiologyandBioinformatics(LCBB)lab.Bernard isoneofthebestadvisorsanyonecangetandIamveryluckytohavehimasmyadvisor.I don’tthinkanyadvisorgivesmorefreedomtohis/herstudentsthanBernarddoes.Bernard gavemealotoffreedomandatthesametimeguidedmewellthroughoutmyPhDwithalotof compassionaswellaspatience.ManytimesIfoundhimmoreasafriendthananadvisorand Ihadmanynon-technicaldiscussionswithhimtoo...especiallyaboutpolitics,governance, andsociety.IamgratefultoBernardformakingmeapartofthislabeventhoughIhada non-CSandnon-Biologybackground.InfactBernardwaskindenoughtocomeallthewayto Indiajusttoattendmywedding!ThankyouBernardforallthatyouhavedoneforme. Moststudentsareluckytohaveonegoodadvisor...butIhadtwo!Dr.PhilippBucherismy otherPhDadvisorandhehasbeenatrulyamazing.Heisapersonwhoisfullofideasandevery timeImethimIlearnedsomethingnew.Hehasbeenverypatientlyandcompassionately helpingmethroughoutthedurationofmyPhD.ThankyouPhilippforeverything. TheGuru-Shishyaparampara(teacher-discipletradition)iswellknowninIndia.Theword "Gu"meansdarknesswhiletheword"Ru"meansdispeller—dispellingdarkness.Guruis thustheonewhoremovesyourignorance. MymotherMrs.VimalaV.N.Pillai—whoIcallAmma—ismyfirstGuru.Amma’sinfinitecom- passion,herloveanddedicationtowardsmywell-beingandeducationisprimarilyresponsible formetocompletemyPhD.Shehasalmostsuper-humanlevelsoftolerancetowardsthemost adversesituationsandherdedicationandsinceritytoeveryoneshemeetsisaconstantsource ofinspirationforme.SheisalsooneofthemostintelligentandinsightfulpeoplethatIknow andIconstantlylookuptoherforadviceandprotection.Idon’tthinkIcouldhaveaskedfora bettermotherthanher.Ifeelextremelyblessedtobeherson. v Acknowledgements MyfatherMr.D.Ullas—whoIcallAchha—hasbeenverylovingandcompassionatetowards me.Achhahasgotanextraordinaryenergyandisfullofgoodhumour.Hehasstruggledalot togivemeagoodeducationandlifeandhasbeenverysupportiveofmycareerdecisions. WithimmensegratitudeIthankAmmaandAchhanforallthattheyhavedoneformeandfor beingmyparents. MybrotherNitinhasalwaysbeenmywell-wisher.Weusedtoplayalottogetherwhenwe werekids,andhadalotoffundoingso.Hehasbeenconstantlysupportiveofme,andbeen mywell-wisher...andIthankhimverymuchforit. IamalsodeeplygratefultomygrandmotherMrs.JanakyAmma(whomIfondlycallAm- mooma)forherblessingsandlovetowardsme. Iwouldalsoliketothankmyotherrelativeswhohavehelpedandadvisedmeandmyfamily alotalongtheway.InparticularIwouldliketoexpressmydeeploveandaffectiontomy cousinsAshwinDinesh(fondlycalledAchhu)andNandana. Eversincemychildhood,whenitcametomyeducation,thingssomehowbymagicseemedto work,asiftheUniversewasaligningitselfinawaysuchthatIgetafineeducation.Iwasvery luckytogetintoagreatschoollikeSt.Joseph’sBoys’HighSchoolinBangalore.Itisoneofthe oldestandfinestschoolsinthecountry.Myparentsstruggledalotandputmeintothisschool althoughitwasbeyondtheirmeans.ApersonnamedShajiwhomIhavenevermetplayeda roleingettingmeadmissionintothisschool.Ithankhimforthat. StudyingatSt.Joseph’sBoys’HighSchoolgavemeanexcellentexposuretotheopportunities outside.IhadaverygoodtimeintheschoolandlearntalotfrommyteacherslikeMrs.Sandhya Raman,Mr.UdayKumar,Dr.DavidChatterjeeandothers.Oneofmyseniorsinschool,the extremelybrightDr.SriramSankararamanhasbeenaconstantsourceofinspirationforme, anditwaspartlybecauseofhimthatIchosetopickcomputationalbiologyasmyareaof research. IwasalsoveryfortunatetostudyatBASEwhichisaveryfinecoachinginstituteforIIT-JEE exams.AlthoughIdidnotmakeitintotheIITs,Ilearntalotbygoingthereandmylovefor physics,organicchemistry,andmathematicsdevelopedquiteabitduringmytimethere.The teachersatBASEandthefounderoftheinstituteDr.H.S.Nagaraja(oftencalledHSN)were peopleofgreatdedicationandsincerity. I would like to thank my B.E. friends — Mushaffa, Manjunath, Karthik, Srinivas for their friendshipduringmyundergraduatedays. Probably the finest moment of my academic life came when I got admission into Indian Institute of Science (IISc), Bangalore for my Masters degree. IISc is one of the oldest and probablythefinestgraduatelevelresearchuniversityinIndia,andIwasveryluckytostudyat theElectricalCommunicationEngineeringdepartmentwhichisoneofthebestdepartments atIISc. vi Acknowledgements IhadagreatadvisorinProf.T.V.SreenivasduringmystudyatIISc.TVSsirwasnotjustagreat advisortechnically,healsotaughtmealotaboutlife.Weusedhavewonderfulphilosophical discussionsandIamextremelygratefultohimforeverythingthathehasdoneforme. At IISc, I also had an opportunity to meet some excellent friends and met some amazing people.Tonameafew,IwouldliketothankSreeram,Basavaraj,Sudha,Anoopandhiswife Anusha,Dinesh,Arun,Manasa,Nadir,Narayana,Venkat,Saikat,Mrugesh,Srirametc.toname afew.IamverygratefultoMrugeshforgettingmeinterestedinyogaandspiritualitybygiving methebook“ThePowerofNow”writtenbyEckhartTolle,whichisthefirstbookonspirituality thatIread. IgotanopportunitytoworkinawonderfulplacelikeMicrosoftResearchIndia(MSRI)fora yearassoonasIfinishedmyMastersdegreeatIISc.IwouldliketothankmyadvisorDr.Navin Goyalforhissupport.IalsothankKalikaBali,Dr.AmitavaDas,andProf.NagasumaR.Chandra whoadvisedmeduringmystaythere.Ialsogotsomegoodfriends—likeCohan,Santhosh, Meena,Sneha.ThroughmyinteractionwithsomeofthemIalsogottomeetLakshmiDinesh whoturnedoutbeanexcellentfriendoveralltheseyears. IrememberlongingtodoaPhDeversincemychildhooddaysandIwasextremelydelightedto getanadmissionintoaworldclassinstitutelikeEPFL.EPFLisawonderfulplaceforresearch andstudy.IhavehadaverybeautifultimeduringmystayinSwitzerland.Iwasluckytobea partoftheLaboratoryofComputationalBiologyandBioinformatics(LCBB),whichwasan excellentplacetobe,thankstoBernardandallmycolleaguesthere.Iwouldliketothanklab matesAvinash,Xiuwei,Wei,Yu,Vaibhav,Mingfu,Cristina,Min,Yann,Krister,Slavica,Olga, Ana,Jelena,Paulina,Laura,Hermina,Aleksandra,Alisaforalltheirfriendshipandsupport. IwasluckytocollaboratewithsomeexceptionallybrightpeopleduringmyPhDdays,other thanmyadvisors.MycollaborationstartedwithAvinashDasSahu,whoisoneofthebrightest andsmartestpersonthatIhavemet;andIdoubtifmyPhDwouldhavehappenedwithouthis supportandimmensehelp.IalsohadgoodcollaborationswithDr.YuLin,Dr.SunilKumar, AnaManasovska,PaulinaGrnarova,JelenaAntic,Prof.JudyABrusslan,Prof.MatteoPellegrini, Dr.VaibhavRajan,LauraHunter,MingfuShao.Ithankthemall. Ihadanopportunitytomentorafewextremelybrightstudents—Ana,Paulina,Jelena,and Laura.Ithankallofthemforgivingmethisopportunity.InfactIamproudtosaythatAna, Paulina,Jelenagottheirfirstpublicationthroughtheircollaborationwithme. IamgratefultoProf.SridharHannenhalli,Prof.WilliamStaffordNoble,Prof.EmreTelatar, Prof.FelixNaefforbeingapartofmyPhDthesisjurycommittee.Alongwithmytwoadvisors BernardandPhilipp,theycarefullyreadmythesisandgivingmevaluablefeedback.Iwould liketothankthemforthat. MylifeinSwitzerlandwouldnothavebeensogreatifitwasn’tforsomeamazingfriendsIhad. InspecificIwouldliketothankmybestfriendsDr.AbhishekTewari,AvinashDasSahu,and Dr.RammohanNarendulawhoIwouldliketokeepintouchthroughoutmylife.Abhishek vii Acknowledgements hasbeenmyclosestfriendthroughoutmyPhDdays.HehadjoinedatthesametimeasIdid, andhestayedintheoppositedoorstudiointhesamebuildingthatIlivedduringmostof myPhDdays.WecookedtogetheronmostdaysandwehadexcellentdiscussionsonIndian politics,society,philosophy,spiritualityetc.InfactAbhishek,Ram,andIusedtotakeactive interestinIndianpoliticsandparticipateinseveralways.Mylifeherewouldhavebeenboring ifnotforAbhishek’sgenuinefriendshipandcompassion.Iamdeeplyindebtedtohimforthat. Avinashisanincrediblepersonwholivesaveryinterestinglife.Heistrulybrilliantandvery goodatmanythings.Otherthanhelpingmealotofresearchandacademicsubjects,Ialso learntalotaboutIndiansocietyandculture,politicsandmanyotherthingsfromhim.Healso helpedalotduringanypersonaldifficultyIhad.Ithankhimforthat.Rambecamemyvery goodfriendduringmylast2-3yearsofPhD.Our“teawithRam”sessionseverydayusedtobe adelightfultime,whenmanyofuswouldmeetforteainRam’slablibraryanddiscussmany things—especiallyIndianpolitics.Ramwasalwaysknownforgettingamazinglycheapoffers anddeals.Heisanavidtraveler,andItraveledalotwithhimaroundSwitzerland. IhadmanyotherwonderfulfriendsatEPFL.RajasunderChandran(Raja)hasbeenagreat friendwhoisdeeplypassionateaboutwhathedoes,andheisverysincere,innocent,and compassionate person. I also enjoyed the friendship of Rahul VV who helped me quite a bit.SomeoftheotherfriendsIwouldliketothankareSuri,Saket,Vandana,Megha,Pankaj, Rishikesh,Arnab,Aviinash,Krishnan,Devikaamongmanyothers. IamgratefultoDevikaforstartingtheGitaself-studygroupanditissomethingIhaveim- menselyenjoyedandlearntalotoverthelastfewyears.Itwastrulyamazingthatfewofus —mainlyDevika,Ram,Abhishek,Raja,Giovanni,Krishnanamongmanyothersmetoncea weekalmosteveryweekforthelasttwoyearsorsoforanhourofGitaclass.Westudiedthe BhagavadGitaHomeStudy(BGHS)coursewrittenbySwamiDayanandaSaraswati.Sofarwe finishedmorethan800pagesofatwo-volumebookwhichisaround1800pages.Giovanni,a ChristianpriestwhoImetduringtheclass,hasbeenagreatfriend.Giovanniisalsoascholar onmanyIndiantextsandIlearntalotfromhim.Heorganizedsomewonderfultravelsto FlorenceandRome,andIlearntalotfromhimduringthesetravels. EPFLandSwitzerlandhasofferedalottome.Otherthangoodeducationandresearchfacilities, EPFLoffersaverygoodPhDstipendwhichhelpedmeandmyfamilyalotfinancially.Coming to Switzerland was very good for me health wise too — I did not suffer from the allergies whichIoftensufferedfrominIndia.IcannotbutbeawedmythebeautyofSwitzerland— thegorgeousmountainsandlakes.IamequallyawedbythecountlessSwissengineersand workerswhomadetheroads,tunnels,railwaysinSwitzerlandtomakethesemountainsso accessibleforus.InfactAmmawhoiscurrentlyinSwitzerlandvisitingmeremarked“God andmanhasstrivedinequalcapacitytomakeSwitzerlandwhatitis”(thisisanapproximate translationofherremarkmadeinMalayalam). ImadesomegreatfriendsviaFacebooklikeVinayVaidyaandDafne(bothofwhomIhave nevermet),andIlearntalotfrommyinteractionswiththem.MydearfriendDr.Sreeram Kannanplayedaveryimportantroleinmylife,especiallyasaspiritualguide.Heintroduced viii Acknowledgements metothe“InnerEngineering”programdesignedbySadhguru.Ithankhimverymuchfor everything. During my PhD, I had an opportunity to attend a semester long program “Mathematical andComputationalApproachesinHighThroughputGenomics,”organizedbyInstituteof PureandAppliedMathematics(IPAM),UniversityofCalifornia,LosAngeles.Iwouldliketo thankIPAMfororganizingsuchagreatprogram.IhadagreattimeinLosAngeles,andan opportunitytocollaboratewithwonderfulresearcherslikeProf.MatteoPellegrini.Ialsogot somegoodfriendslikeDr.GregRyslik. I would like to thank my in-laws Mrs. T.V. Meera Nambiar (who I call Mummy), Mr. E.K. KrishnanNambiar(whoIcallDaddy)foralltheirloveandsupport;andforallowingmetobe Asha’shusband.IwouldalsoliketothankAsha’sbrotherMr.AnuKrishnaforallhissupport andcompassion. IamdeeplygratefultomylovelywifeDr.AshaKrishna.Wehadanarrangedmarriage,and didnotreallyknoweachotherwellbeforethewedding.WegotmarriedonJanuary8th,2014; andthelastfewmonthshasbeenamongthebestinmylife.Ashahasbeenthemostloving andcompassionatewife.Iconsidermyselffortunatetoreceiveherloveandaffection,and considermyselfluckytobeherhusband.Thankyoumutheeforeverything. I humbly bow to the great Masters of Yoga to whom I am ever grateful. In India, among all human relationships, the relationship between a Guru (spiritual Master) and Shishya (student/seeker)isconsideredthehighest.Becauseitistheonlyrelationshipwhichistruly onesided—inthataGuruonlygiveswithoutexpectinganythinginreturnfromthestudent except the student’s growth, while a student only takes without having anything to offer in return. I learnta lot from studyingthe teachings of great Masters ofYoga(andAdvaita Vendanta or nondualism) like Bhagavan Sri Ramana Maharshi, Sri Nisargadatta Maharaj, EckhartTolle,amongmanyothers,andbyreadingsomeofthecommentaryoftheSashtras bySwamiDayanandaSaraswati.IamdeeplygratefultoalltheancientGuruswhowalkedon thisplanetallthewayuptothefirstGuruortheAdiguru—AdiyogiShiva—whoisworshiped asDakshinamurthy,theSouth-facingJnanaaspectofShiva.IguessIamblessedtobeborn inIndiawhichhasanextraordinaryspiritualtradition.AndIammostgratefultoSadhguru JaggiVasudevforbeingmyMaster.SadhgurucameintomylifewhenIwaslookingforaliving Master. FinallyIthanktheGreatestGuruofthemall—Life. Lausanne,August28,2014 NishanthUlhasNair ix