Motif Search in Graphs

-

English
35 Pages
Read an excerpt
Gain access to the library to view online
Learn more

Description

Motif Search in Graphs: Application to Metabolic Networks Vincent Lacroix 1,2,?, Cristina G. Fernandes 3, Marie-France Sagot 1,2,4 1 Equipe BAOBAB, Laboratoire de Biometrie et Biologie Evolutive (UMR 5558);CNRS; Univ. Lyon 1, 43 bd 11 nov, 69622, Villeurbanne Cedex, France. 2 Projet Helix, INRIA Rhone-Alpes, 655 avenue de l'Europe, 38330 Montbonnot Saint-Martin, France 3 Instituto de Matematica e Estatıstica, Universidade de Sa˜o Paulo,Rua do Mata˜o, 1010, Cidade Universitaria, CEP 05508-090, Sa˜o Paulo, Brazil 4 Department of Computer Science, King's College London, Strand, London WC2R 2LS, England ? Corresponding author () Abstract The classic view of metabolism as a collection of metabolic pathways is being questioned with the currently available possibility of studying whole networks. Novel ways of decomposing the network into modules and motifs that could be considered as the building blocks of a network are being sug- 1

  • provides no

  • protein protein

  • motif has

  • no clear definition

  • networks

  • taken into consideration

  • been proposed


Subjects

Informations

Published by
Reads 8
Language English
Report a problem
MotifSearchinGraphs:ApplicationtoMetabolicNetworksVincentLacroix1,2,,CristinaG.Fernandes3,Marie-FranceSagot1,2,41E´quipeBAOBAB,LaboratoiredeBiom´etrieetBiologieEvolutive(UMR5558);CNRS;Univ.Lyon1,43bd11nov,69622,VilleurbanneCedex,France.2ProjetHelix,INRIARhˆone-Alpes,655avenuedel'Europe,38330MontbonnotSaint-Martin,France3InstitutodeMatema´ticaeEstat´stica,UniversidadedeS˜aoPaulo,RuadoMat˜ao,1010,CidadeUniversita´ria,CEP05508-090,S˜aoPaulo,Brazil4DepartmentofComputerScience,King'sCollegeLondon,Strand,LondonWC2R2LS,EnglandCorrespondingauthor(lacroix@biomserv.univ-lyon1.fr)AbstractTheclassicviewofmetabolismasacollectionofmetabolicpathwaysisbeingquestionedwiththecurrentlyavailablepossibilityofstudyingwholenetworks.Novelwaysofdecomposingthenetworkintomodulesandmotifsthatcouldbeconsideredasthebuildingblocksofanetworkarebeingsug-1
gested.Inthiswork,weintroduceanewdenitionofmotifinthecontextofmetabolicnetworks.Unlikeinpreviousworkson(other)biochemicalnetworks,thisdenitionisnotbasedonlyontopologicalfeatures.Wepro-poseinsteadtouseanalternativedenitionbasedonthefunctionalnatureofthecomponentsthatformthemotif,whichwecallareactionmotif.Afterintroducingaformalframeworkmotivatedbybiologicalconsiderations,wepresentcomplexityresultsontheproblemofsearchingforalloccurrencesofareactionmotifinanetwork,andintroduceanalgorithmthatisfastinpracticeinmostsituations.Wethenshowaninitialapplicationtothestudyofpathwayevolution.Finally,wegivesomegeneralfeaturesoftheob-servednumberofoccurrencesinordertohighlightsomestructuralfeaturesofmetabolicnetworks.1IntroductionNetworkbiologyisageneraltermforanemergingeldthatconcernsthestudyofinteractionsbetweenbiologicalelements[1].Thetermmolecularinterac-tionnetworksmaydesignateseveraltypesofnetworksdependingonthekindofmoleculesinvolved.Classically,onedistinguishesbetweengeneregulatorynetworks,signaltransductionnetworksandmetabolicnetworks.Protein-proteininteractionnetworksrepresentyetanothertypeofnetwork,butthistermisratherlinkedtothetechniques(suchasYeast-2-hybrid)usedtoproducethedataand2
coverspossiblyseveralbiologicalprocesses(including,forexample,theforma-tionofcomplexesandphosphorylationcascades)[15].Oneofthedeclaredobjectivesofnetworkbiology(orsystemsbiologyingen-eral)iswholecellsimulation[8].However,studyingthedynamicsofanetworkrequiresknowledgeonreactionmechanismssuchasthekineticparametersde-scribingaMichaelis-Mentenequation.Besidesthefactthatsuchknowledgeisoftenunavailableorunreliable,thestudyofthestaticsetofreactionsthatcon-stituteabiochemicalnetworkisequallyimportant,bothasarststeptowardsintroducingdynamics,andinitself.Indeed,suchstaticsetrepresentsnotwhatishappeningatagiventimeinagivencellbutinsteadthecapabilitiesofthecell,in-cludingcapabilitiesthecelldoesnotuse.Acarefulanalysisofthissetofreactionsforagivenorganism,aloneorincomparisonwiththesetofotherorganisms,mayalsohelptoarriveatabetterunderstandingofhowmetabolismevolves.Itisthissetweproposetostudyinthispaper.Moreprecisely,inthefollowingsections,theterm“metabolism”shouldbeunderstoodasthestaticsetofreactionsinvolvedinthesynthesisanddegradationofsmallmolecules.Regulationinformationisnottakenintoconsiderationfornow.Itmaybeaddedinalaterstep,asthe“software”runningonthe“hardware”ofametabolicnetwork[14].Amajorissueconcerningthestudyofbiochemicalnetworksistheproblemoftheirorganisation.Severalattemptshavebeenmadetodecomposecomplexnetworksintoparts.These“parts”havebeencalledmodulesormotifs,butno3