文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > BIOINFORMATICS ORIGINAL PAPER Data and text mining SAGA a subgraph matching tool for biolog
侵权投诉

BIOINFORMATICS ORIGINAL PAPER Data and text mining SAGA a subgraph matching tool for biolog

doi:10.1093/bioinformatics/btl571

Y.Tianetal.

labeltobeassociatedwithmorethanonegroup.Nodescanthenbecomparedbasedonthegrouplabels.Thismodelofnodecomparisonisquitegeneralandpracticalformanybiologicalapplications.Forexample,thefunctionalsimilaritybetweentwoenzymescanbedeterminedbasedonthelengthofthecommonpre xofthecorrespondingEnzymeCommission(EC)numbers.Forgeneralproteins,onecanusedatabaseslikeKEGG(Kanehisaetal.,2006)andCOG(Tatusovetal.,1997)whichorganizeproteinsintoorthologousgroups,andconsidertwoproteinstobefunction-allysimilaronlyiftheyareinthesamegroup.Thismismatchmodelcanalsobegeneralizedtoothersettings,suchascomparingnodesbelongingtodifferentclassesbasedonthepositionsofthetwoclassesinaclassi cationhierarchy,suchasGeneOntology(doc.guandang.net).

Weutilizetheconceptoforthologousgroupsforournodemismatchmodel.Themappingfromanodelabeltoasetoforthologousgroups,allowinganodetobelongtomorethanoneorthologousgroup,isde nedasr:L!P(GL),whereListhesetofnodelabels,GListhesetofgrouplabels,andP(GL)isthepowersetofGL.Underthismodel,mismatch(Li,Lj)¼1ifr(Li)\r(Lj)¼;,andmismatch(Li,Lj)<1,otherwise.

TheNodeGapscomponentin

Equation(4)measuresthepenaltiesassociatedwiththegapnodesinthequerygraph,therebyfavoringmatchesthathavefewergapnodes.Inourmodel,differentnodesinthequerygraphcanhavedifferentpenaltyvalues,andnodeswiththesamelabelcanhavedifferentpenaltiesaswell.

Themodelalsogivesusersthefreedomtochoosebetweengappedmatches(matchesthatallowgapnodes)andungappedmatches.IfgapG(u)issetto1foreverynode,thenthemodelonlysupportsungappedmatches,otherwiseitallowsgappedmatches.

Forsimplicity,fortherestofthediscussion,wewillassumethatallnodeshavethesamegappenaltyvaluedenotedasSingleGapCost.

Oursub-graphmatchingmodelisvery exibleandallowsforincorporationofdomainknowledgeintothescoringcriteria.Theonlyrestrictionisthatthegappenaltymustbepositiveandthemismatchpenaltymustbenon-negative.Theserestrictionsensurethatthesubgraphdistanceisanon-negativevalue.Withtheserestrictions,ifthequerygraphissubgraph-isomorphictothetargetgraph,thesubgraphdistanceis0,andviceversa.

2.2.3TheNodeGapscomponent

edges.Usingthisheuristic,wecandramaticallyreducethesizeoftheFragmentIndex.

Notethatincontrasttoexistingmethods,whichindexconnectedsubgraphs,thefragmentsinSAGAdonotalwayscorrespondtoconnectedsubgraphs.Thereasonforusingthemoregeneralde nitionoffragmentsistoallownodegapsinthematchmodel.Forexample,inFigure1(b),nodes 3and 4inG1canbematchedtonodes 3and 4inG2,respectively.Although 3and 4donotformaconnectedsubgraphinG2,theycorrespondtoafragmentthatneedstobeindexedsothatthismatchcanbedetected.AnentryintheFragmentIndexhasthefollowingformat:{nodeSeq,groupSeq,distSeq,sumDist,gid},wherenodeSeqisthesequenceofnodeIDsforthenodesinthefragment,groupSeqisthesequenceofgrouplabelsassociatedwiththenodes,distSeqisthesequenceofpairwisedistancesbetweenthenodesinthefragment,sumDististhesumofthesepairwisedistances,andgidisauniquegraphID.Recallthatanodelabelcanbeassociatedwithmultiplegrouplabels.Inthiscase,wegenerateallpossiblegrouplabelsequencesforafragment,andindexeachone.AnexampleshowingtheFragmentIndexonasampledatabaseispresentedinSection1ofthesupplementalmaterial.

Toef cientlyevaluatethesubgraphdistancebetweenaquerygraphandadatabasegraph,anadditionalindexcalledDistanceIndexisalsomain-tained.Thisindexisusedtolookuptheprecomputeddistancebetweenanypairofnodesinagraph(Section2.2.1).

2.3.2ThematchingalgorithmThematchingalgorithmproceedsasfollows:First,thequeryisbrokenintosmallfragmentsandtheFragmentIndexisprobed.Then,thehitsfromtheindexprobesarecombinedtoproducelargercandidatematches.Finally,eachcandidateisexaminedtoproducetheactualresults.Eachofthesethreestepsisdescribedindetailbelow.

Step1: ndingsmallhits.Inthisstep,thequeryisbrokenintosmallfragmentsandtheFragmentIndexisprobedto nddatabasefragmentsthataresimilartothequeryfragments.

Giventhequery,fragments(k-nodesets)areenumeratedinthesamewayaswedidforthedatabasegraphs.Next,foreachqueryfragment,thegroupSeq,nodeSeq,sumDist,anddistSeqvaluesarecomputed.Then,theFragmentIndexisprobedwitheachofthesequeryfragments.

Theactualindexprobeusesthefollowingmulti-level lteringstrategy:First,thegroupSeqandsumDistvaluesareusedto lteroutfragmentsthatcannotmatch.Next,additionalfalsepositivesareremovedusingthedistSeqvalues.

Inthe rstlevelof ltering,databasefragmentsarefetchedonlyiftheyhavethesamegroupSeqasthequeryfragmentandtheirsumDistvaluesarewithinthesafeboundsthatwehavedeveloped.Formally,theprobecriteriais:ftjt2FragmentIndex t:groupSeq¼fq:groupSeq fq:sumDistÀ

MaxPairDist

e

kðkÀ1Þ

2.2.4Characteristicsofthesubgraphdistancemodel

2.3Theindex-basedmatchingalgorithm

¨vetechniqueforevaluatingsubgraphmatchingqueriesistocompareAna

thequerywitheverygraphinthedatabaseandreportthematches,whichisprohibitivelyexpensive.Weproposeanovelindex-basedheuristicalgorithmthatallowsforamuchfasterevaluationoftheapproximatesubgraphmatchingoperation.

First,anindexisbuiltonsmallsubstructuresofgraphsinthedatabase.Thisindexisthenusedtomatchfragmentsofthequerywithfragmentsinthedatabase.Finally,thematchingfragmentsareassembledintolargermatches.Theactualmethodisdescribedindetailbelow.

Theindexonsmallsubstructuresof

graphsinthedatabaseiscalledtheFragmentIndex.Itisprobedbythematchingalgorithmtoproducehitsforsubstructuresinthequery.

Theindexingunitisasetofknodesfromthegraphsinthedatabase.Wecalleachsuchsetafragment.Herekisauserspeci edparameter,andisusuallyasmallnumberlike2,3or4.However,simplyenumeratingallpossiblek-nodesetsisexpensiveintermsofbothtimeandspace.Atthesametime,ifanypairofnodesinafragmentistoofarapartbythepairwisedistancemeasure(refertoSection2.2.1),thisfragmentdoesnotcorrespondtoameaningfulsubstructure,thusisnotworthindexing.Therefore,aparameterdmaxisspeci edtocontrolwhetherafragmentistobeindexed.Foragivenk-nodesetv1,v2,...,vk,ifanytwonodesviandvjsatisfyd(vi,vj) dmax,weconnectthetwonodesbyapseudoedge.Then,weindexthisfragmentonlyiftheknodesformaconnectedgraphbythepseudo

·

2.3.1Theindexstructures

À1Þ

t:sumDist fq:sumDist+kðk·MaxPairDistg wherefqisthee

queryfragment,andkisthefragmentsize.MaxPairDistisauser-de nedparameterwhichrestrictstheweightedpairwisedistancedifferencebetweenthequeryandthedatabasefragmentsaswe·jdG1ðu vÞÀdG2ðlu lvÞj MaxPairDist.(SeeSection2ofthesupplementalmaterialfordetails.)Afterthe rstlevelof ltering,wegetalistofcandidatedatabasefrag-mentsforeveryqueryfragment.Thislistcanbefurtherre nedbyusingthedistSeqinformation(whichcontainsthepairwisedistances)tocheckthatallpairwisedistancessatisfytheMaxPairDistcriterionde nedabove.

Step2:assemblingsmallhits.Step1producesasetofsmallfragmenthits.Thesesmallerhitsareassembledintobiggermatchesasfollows:First,thehitsaregroupedbythedatabasegraphIDs.Then,ahit-compatiblegraphisbuiltforeachmatchinggraph.Eachnodeinahit-compatiblegraphcorrespondstoapairofmatchingqueryanddatabasefragments.Anedgeisdrawnbetweentwonodesinthehit-compatiblegraphifandonlyiftwoqueryfragmentsshare0ormorenodes,andthecorrespondingdata-basefragmentsinthehit-compatiblegraphalsosharethesamecorrespond-ingnodes.Anedgebetweentwonodestellsusthatthecorrespondingtwo

234

上一页第3页

你可能喜欢

热门文档

相关文档

  • Bioinformatics

    ren Brunank , Bioinformatics:The Machine Learning Approach, A Bradford Book, The MIT press ,Cambridge, Massachusetts,London,England ,1998 [6] Eric ...

  • Bioinformatics

    49页 免费 Bioinformatics 06_swis... 30页 免费 bioinformatics-1 暂无评价 74页 2下载券 bioinformatics softwar... 13页 免费喜欢此文档的还喜欢...

  • bioinformatics-3

    Bioinformatics 65页 免费bioinformatics-3 暂无评价0人阅读0次下载举报文档§2.3 核酸...

  • Bioinformatics

    Bioinformatics_lect_1_理学_高等教育_教育专区。生物信息学 pptBioinformatics 主讲人: 陈海峰 主讲人 Shanghai Jiaotong University 2011-11-13 1 Contact ...

  • bioinformatics-4

    bioinformatics-4_农学_高等教育_教育专区。生物信息学§2.4 核酸序列的多序列比对 目的: ? 发现多个序列的共性 ? 发现与结构和功能相关的保守序列片段设:有k...

  • Bioinformatics 01

    免费 Bioinformatics 09_blast(... 暂无评价 50页 免费 Bioinformatics 03_genban... 暂无评价 46页 免费 Bioinformatics 04_DNA co... 暂无评价 49页 免费...

  • bioinformatics-4

    bioinformatics-4 隐藏>> §2.4 核酸序列的多序列比对 目的: ? 发现多个序列的共性 ? 发现与结构和功能相关的保守序列片段设:有k个序列s1, s2, ... ,...

  • bioinformatics.btu635

    bioinformatics.btu635_生物学_自然科学_专业资料。宏基因功能分析中特征选择和比较的二级统计程序Bioinformatics Advance Access published September 24, 2014 Genome ...

  • Bioinformatics-2010-Arends-2990-2

    BIOINFORMATICS APPLICATIONS NOTE Genetics and population analysis Vol. 26 no. 23 2010, pages 2990–2992 doi:10.1093/bioinformatics/btq565 Advance Access ...

  • BIOINFORMATICS BicAT A Biclustering Analysis Toolbox

    Bioinformatics Advance Access published March 21, 2006 BIOINFORMATICS BicAT: A Biclustering Analysis Toolbox Simon Barkow a? Stefan Bleuler a , Amela Preli?...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email