Motif Search in Graphs

pages

English

Documents

Écrit par
Vincent Lacroix

Publié par
profil-urra-2012

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Découvre YouScribe et accède à tout notre catalogue !

Je m'inscris

Découvre YouScribe et accède à tout notre catalogue !

Je m'inscris

pages

English

Documents

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Publié par

profil-urra-2012

Langue

English

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

Voir

Publié par

profil-urra-2012

Langue

English

Europe Lacroix

MotifSearchinGraphs:ApplicationtoMetabolicNetworksVincentLacroix1,2,⋄,CristinaG.Fernandes3,Marie-FranceSagot1,2,41E´quipeBAOBAB,LaboratoiredeBiom´etrieetBiologieEvolutive(UMR5558);CNRS;Univ.Lyon1,43bd11nov,69622,VilleurbanneCedex,France.2ProjetHelix,INRIARhone-Alpes,655avenuedel'Europe,38330MontbonnotSaint-Martin,France3InstitutodeMatema´ticaeEstat´stica,UniversidadedeSaoPaulo,RuadoMatao,1010,CidadeUniversita´ria,CEP05508-090,SaoPaulo,Brazil4DepartmentofComputerScience,King'sCollegeLondon,Strand,LondonWC2R2LS,England⋄Correspondingauthor(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,thetermmetabolismshouldbeunderstoodasthestaticsetofreactionsinvolvedinthesynthesisanddegradationofsmallmolecules.Regulationinformationisnottakenintoconsiderationfornow.Itmaybeaddedinalaterstep,asthesoftwarerunningonthehardwareofametabolicnetwork[14].Amajorissueconcerningthestudyofbiochemicalnetworksistheproblemoftheirorganisation.Severalattemptshavebeenmadetodecomposecomplexnetworksintoparts.Thesepartshavebeencalledmodulesormotifs,butno3

Voir