J. Comput. Biol. - The approximability of shortest path-based graph orientations of protein-protein interaction networks.

Tópicos

{ structur(1116) can(940) graph(676) }
{ problem(2511) optim(1539) algorithm(950) }
{ method(1219) similar(1157) match(930) }
{ network(2748) neural(1063) input(814) }
{ data(2317) use(1299) case(1017) }
{ gene(2352) biolog(1181) express(1162) }
{ learn(2355) train(1041) set(1003) }
{ method(984) reconstruct(947) comput(926) }
{ patient(2837) hospit(1953) medic(668) }
{ cost(1906) reduc(1198) effect(832) }
{ sampl(1606) size(1419) use(1276) }
{ first(2504) two(1366) second(1323) }
{ use(1733) differ(960) four(931) }
{ inform(2794) health(2639) internet(1427) }
{ imag(1057) registr(996) error(939) }
{ featur(3375) classif(2383) classifi(1994) }
{ studi(2440) review(1878) systemat(933) }
{ assess(1506) score(1403) qualiti(1306) }
{ method(1557) propos(1049) approach(1037) }
{ system(1050) medic(1026) inform(1018) }
{ compound(1573) activ(1297) structur(1058) }
{ studi(1119) effect(1106) posit(819) }
{ group(2977) signific(1463) compar(1072) }
{ data(3008) multipl(1320) sourc(1022) }
{ intervent(3218) particip(2042) group(1664) }
{ patient(1821) servic(1111) care(1106) }
{ use(2086) technolog(871) perceiv(783) }
{ high(1669) rate(1365) level(1280) }
{ detect(2391) sensit(1101) algorithm(908) }
{ model(3404) distribut(989) bayesian(671) }
{ can(774) often(719) complex(702) }
{ imag(1947) propos(1133) code(1026) }
{ data(1737) use(1416) pattern(1282) }
{ system(1976) rule(880) can(841) }
{ measur(2081) correl(1212) valu(896) }
{ bind(1733) structur(1185) ligand(1036) }
{ sequenc(1873) structur(1644) protein(1328) }
{ imag(2830) propos(1344) filter(1198) }
{ imag(2675) segment(2577) method(1081) }
{ patient(2315) diseas(1263) diabet(1191) }
{ take(945) account(800) differ(722) }
{ motion(1329) object(1292) video(1091) }
{ treatment(1704) effect(941) patient(846) }
{ surgeri(1148) surgic(1085) robot(1054) }
{ framework(1458) process(801) describ(734) }
{ error(1145) method(1030) estim(1020) }
{ chang(1828) time(1643) increas(1301) }
{ concept(1167) ontolog(924) domain(897) }
{ clinic(1479) use(1117) guidelin(835) }
{ algorithm(1844) comput(1787) effici(935) }
{ extract(1171) text(1153) clinic(932) }
{ data(1714) softwar(1251) tool(1186) }
{ design(1359) user(1324) use(1319) }
{ control(1307) perform(991) simul(935) }
{ model(2220) cell(1177) simul(1124) }
{ care(1570) inform(1187) nurs(1089) }
{ general(901) number(790) one(736) }
{ search(2224) databas(1162) retriev(909) }
{ featur(1941) imag(1645) propos(1176) }
{ case(1353) use(1143) diagnosi(1136) }
{ howev(809) still(633) remain(590) }
{ data(3963) clinic(1234) research(1004) }
{ studi(1410) differ(1259) use(1210) }
{ risk(3053) factor(974) diseas(938) }
{ perform(999) metric(946) measur(919) }
{ research(1085) discuss(1038) issu(1018) }
{ import(1318) role(1303) understand(862) }
{ model(2341) predict(2261) use(1141) }
{ visual(1396) interact(850) tool(830) }
{ perform(1367) use(1326) method(1137) }
{ blood(1257) pressur(1144) flow(957) }
{ spatial(1525) area(1432) region(1030) }
{ record(1888) medic(1808) patient(1693) }
{ health(3367) inform(1360) care(1135) }
{ model(3480) simul(1196) paramet(876) }
{ monitor(1329) mobil(1314) devic(1160) }
{ ehr(2073) health(1662) electron(1139) }
{ state(1844) use(1261) util(961) }
{ research(1218) medic(880) student(794) }
{ model(2656) set(1616) predict(1553) }
{ age(1611) year(1155) adult(843) }
{ medic(1828) order(1363) alert(1069) }
{ signal(2180) analysi(812) frequenc(800) }
{ activ(1138) subject(705) human(624) }
{ time(1939) patient(1703) rate(768) }
{ can(981) present(881) function(850) }
{ analysi(2126) use(1163) compon(1037) }
{ health(1844) social(1437) communiti(874) }
{ cancer(2502) breast(956) screen(824) }
{ use(976) code(926) identifi(902) }
{ drug(1928) target(777) effect(648) }
{ result(1111) use(1088) new(759) }
{ implement(1333) system(1263) develop(1122) }
{ survey(1388) particip(1329) question(1065) }
{ estim(2440) model(1874) function(577) }
{ decis(3086) make(1611) patient(1517) }
{ process(1125) use(805) approach(778) }
{ activ(1452) weight(1219) physic(1104) }
{ method(1969) cluster(1462) data(1082) }
{ method(2212) result(1239) propos(1039) }

Resumo

The graph orientation problem calls for orienting the edges of an undirected graph so as to maximize the number of prespecified source-target vertex pairs that admit a directed path from the source to the target. Most algorithmic approaches to this problem share a common preprocessing step, in which the input graph is reduced to a tree by repeatedly contracting its cycles. Although this reduction is valid from an algorithmic perspective, the assignment of directions to the edges of the contracted cycles becomes arbitrary and, consequently, the connecting source-target paths may be arbitrarily long. In the context of biological networks, the connection of vertex pairs via shortest paths is highly motivated, leading to the following variant: Given an undirected graph and a collection of source-target vertex pairs, assign directions to the edges so as to maximize the number of pairs that are connected by a shortest (in the original graph) directed path. Here we study this variant, provide strong inapproximability results for it, and propose approximation algorithms for the problem, as well as for relaxations where the connecting paths need only be approximately shortest.

Resumo Limpo

graph orient problem call orient edg undirect graph maxim number prespecifi sourcetarget vertex pair admit direct path sourc target algorithm approach problem share common preprocess step input graph reduc tree repeat contract cycl although reduct valid algorithm perspect assign direct edg contract cycl becom arbitrari consequ connect sourcetarget path may arbitrarili long context biolog network connect vertex pair via shortest path high motiv lead follow variant given undirect graph collect sourcetarget vertex pair assign direct edg maxim number pair connect shortest origin graph direct path studi variant provid strong inapproxim result propos approxim algorithm problem well relax connect path need approxim shortest

Resumos Similares

IEEE Trans Image Process - Constrained and dimensionality-independent path openings. ( 0,862991796105496 )
Comput Biol Chem - On topological indices for small RNA graphs. ( 0,844189883924545 )
IEEE Trans Image Process - 3-D curvilinear structure detection filter via structure-ball analysis. ( 0,816221838643439 )
Neural Comput - Intrinsic graph structure estimation using graph Laplacian. ( 0,805382906485915 )
IEEE Trans Vis Comput Graph - Output-Sensitive Construction of Reeb Graphs. ( 0,803812561060537 )
AMIA Annu Symp Proc - Synergism between the mapping projects from SNOMED CT to ICD-10 and ICD-10-CM. ( 0,797826443395741 )
Comput Methods Programs Biomed - TreeVis: a MATLAB-based tool for tree visualization. ( 0,792145087130938 )
Neural Comput - A network of spiking neurons for computing sparse representations in an energy-efficient way. ( 0,782296514690022 )
IEEE Trans Pattern Anal Mach Intell - A Robust O(n) Solution to the Perspective-n-Point Problem. ( 0,75873984948399 )
IEEE Trans Pattern Anal Mach Intell - The Sum-over-Forests Density Index: Identifying Dense Regions in a Graph. ( 0,758215904236493 )
IEEE Trans Vis Comput Graph - Visual Analysis of Large Graphs Using (X,Y)-clustering and Hybrid Visualizations. ( 0,75342041903343 )
IEEE Trans Vis Comput Graph - Flow Visualization with Quantified Spatial and Temporal Errors Using Edge Maps. ( 0,753235121074561 )
IEEE Trans Vis Comput Graph - Image-Based Modeling of Unwrappable Fa?ades. ( 0,748096312664323 )
IEEE Trans Pattern Anal Mach Intell - Trinary-Projection Trees for Approximate Nearest Neighbor Search. ( 0,744450794361079 )
J Biomed Inform - Tree kernel-based protein-protein interaction extraction from biomedical literature. ( 0,743120383965698 )
J. Comput. Biol. - Pathset graphs: a novel approach for comprehensive utilization of paired reads in genome assembly. ( 0,74239051967478 )
IEEE Trans Pattern Anal Mach Intell - Graph Regularized Nonnegative Matrix Factorization for Data Representation. ( 0,73597116471785 )
IEEE Trans Pattern Anal Mach Intell - C^4: Exploring Multiple Solutions in Graphical Models by Cluster Sampling. ( 0,732874179564894 )
Comput. Biol. Med. - Hyperbolic Dirac Nets for medical decision support. Theory, methods, and comparison with Bayes Nets. ( 0,73018311113447 )
Brief. Bioinformatics - Structural mapping: how to study the genetic architecture of a phenotypic trait through its formation mechanism. ( 0,729592761653156 )
IEEE Trans Vis Comput Graph - The Design Space of Implicit Hierarchy Visualization: A Survey. ( 0,712966890342025 )
IEEE Trans Image Process - Demosaicking by alternating projections: theory and fast one-step implementation. ( 0,702816214087779 )
Comput Math Methods Med - Particle system based adaptive sampling on spherical parameter space to improve the MDL method for construction of statistical shape models. ( 0,702385166481385 )
J Chem Inf Model - Characterization of heterocyclic rings through quantum chemical topology. ( 0,700739018865558 )
IEEE Trans Image Process - Hyperspectral image representation and processing with binary partition trees. ( 0,697985111393569 )
IEEE Trans Image Process - Coding order decision of B frames for rate-distortion performance improvement in single-view video and multiview video coding. ( 0,69716749346245 )
Comput. Biol. Med. - Forest classification trees and forest support vector machines algorithms: Demonstration using microarray data. ( 0,695793211053565 )
IEEE Trans Pattern Anal Mach Intell - An Extended Path Following Algorithm for Graph-Matching Problem. ( 0,689546317571097 )
IEEE Trans Image Process - On the construction of topology-preserving deformation fields. ( 0,68865713369056 )
IEEE Trans Vis Comput Graph - Grouper: A Compact, Streamable Triangle Mesh Data Structure. ( 0,685436889309184 )
Brief. Bioinformatics - Computational methods for Gene Orthology inference. ( 0,684983371233614 )
IEEE Trans Image Process - Stereo matching and view interpolation based on image domain triangulation. ( 0,683290971806336 )
J Chem Inf Model - Beyond terrestrial biology: charting the chemical universe of a-amino acid structures. ( 0,682472315106327 )
IEEE Trans Image Process - The elastic ratio: introducing curvature into ratio-based image segmentation. ( 0,679975901639997 )
IEEE Trans Image Process - Ridge network detection in crumpled paper via graph density maximization. ( 0,675694621418398 )
Comput. Biol. Med. - Automating fault tolerance in high-performance computational biological jobs using multi-agent approaches. ( 0,675296823122446 )
IEEE Trans Vis Comput Graph - Dynamic Network Visualization with Extended Massive Sequence Views. ( 0,670756330913798 )
Int J Med Inform - Use of order sets in inpatient computerized provider order entry systems: a comparative analysis of usage patterns at seven sites. ( 0,669034162730616 )
J Med Syst - Manual refinement system for graph-based segmentation results in the medical domain. ( 0,664750344448583 )
IEEE Trans Image Process - Edge-preserving image regularization based on morphological wavelets and dyadic trees. ( 0,663189911704575 )
J. Comput. Biol. - Simultaneous folding of alternative RNA structures with mutual constraints: an application to next-generation sequencing-based RNA structure probing. ( 0,663037698382022 )
Neural Comput - Refined rademacher chaos complexity bounds with applications to the multikernel learning problem. ( 0,663005361577954 )
IEEE Trans Vis Comput Graph - A Whole Surface Approach to Crowd Simulation on Arbitrary Topologies. ( 0,662798162053545 )
IEEE Trans Image Process - Topology preserving warping of 3-D binary images according to continuous one-to-one mappings. ( 0,661179604907286 )
J. Comput. Biol. - Random matrix approach to the distribution of genomic distance. ( 0,658325929417097 )
IEEE Trans Image Process - A co-saliency model of image pairs. ( 0,658282619259581 )
J. Comput. Biol. - Shapes of RNA pseudoknot structures. ( 0,657997599568905 )
IEEE Trans Image Process - W-tree indexing for fast visual word generation. ( 0,656105101631298 )
IEEE Trans Image Process - Toward a unified color space for perception-based image processing. ( 0,653858626071214 )
IEEE Trans Vis Comput Graph - Uncluttered Single-Image Visualization of Vascular Structures Using GPU and Integer Programming. ( 0,653828499953583 )
J Med Syst - Energy-aware Gateway Selection for increasing the lifetime of Wireless Body Area Sensor Networks. ( 0,650824841042213 )
J. Comput. Biol. - A polynomial-time algorithm computing lower and upper bounds of the rooted subtree prune and regraft distance. ( 0,646929450575299 )
IEEE Trans Neural Netw Learn Syst - MTC: A Fast and Robust Graph-Based Transductive Learning Method. ( 0,646554550587378 )
IEEE Trans Image Process - Connected filtering based on multivalued component-trees. ( 0,644899326689586 )
IEEE Trans Vis Comput Graph - Graph Drawing Aesthetics — Created by Users not Algorithms. ( 0,642107444255488 )
IEEE Trans Image Process - Design and optimization of color lookup tables on a simplex topology. ( 0,641216445521181 )
J. Comput. Biol. - Counting RNA pseudoknotted structures. ( 0,640080507356158 )
J. Comput. Biol. - Re-evaluating the rules of protein topology. ( 0,635044171160539 )
IEEE Trans Image Process - A Geometric Framework for Rectangular Shape Detection. ( 0,632166930964664 )
IEEE Trans Image Process - Including the Size of Regions in Image Segmentation by Region-Based Graph. ( 0,624847472059433 )
IEEE Trans Pattern Anal Mach Intell - Learning AND-OR Templates for Object Recognition and Detection. ( 0,623783388282218 )
J. Comput. Biol. - Paired de bruijn graphs: a novel approach for incorporating mate pair information into genome assemblers. ( 0,623087003156543 )
Comput. Biol. Med. - Effect of bunching of cilia and their interplay on muco-ciliary transport. ( 0,622339168099506 )
Neural Comput - Parametric inference in the large data limit using maximally informative models. ( 0,620767059094052 )
J. Comput. Biol. - Finding maximum colorful subtrees in practice. ( 0,620614437296577 )
J. Comput. Biol. - Exactly computing the parsimony scores on phylogenetic networks using dynamic programming. ( 0,616809308328123 )
Int J Comput Assist Radiol Surg - Complete fully automatic model-based segmentation of normal and pathological lymph nodes in CT data. ( 0,615912085333626 )
J Chem Inf Model - Time-averaged distributions of solute and solvent motions: exploring proton wires of GFP and PfM2DH. ( 0,615464943624502 )
IEEE Trans Image Process - Anisotropic morphological filters with spatially-variant structuring elements based on image-dependent gradient fields. ( 0,605856070968883 )
IEEE Trans Neural Netw Learn Syst - Multitask Classification Hypothesis Space With Improved Generalization Bounds. ( 0,604796402539392 )
Comput Methods Programs Biomed - Automatic detection and characterisation of retinal vessel tree bifurcations and crossovers in eye fundus images. ( 0,603325234214693 )
Comput. Biol. Med. - Probing brain connectivity by combined analysis of diffusion MRI tractography and electrocorticography. ( 0,602955549634905 )
IEEE Trans Pattern Anal Mach Intell - Building Development Monitoring in Multitemporal Remotely Sensed Image Pairs with Stochastic Birth-Death Dynamics. ( 0,600136845594595 )
Neural Comput - Temporal order detection and coding in nervous systems. ( 0,600129094906226 )
Neural Comput - Simple neural-like p systems for maximal independent set selection. ( 0,597505926978392 )
J Biomed Inform - Decision support from local data: creating adaptive order menus from past clinician behavior. ( 0,597411115136745 )
IEEE Trans Neural Netw Learn Syst - Kernel reconstruction ICA for sparse representation. ( 0,597266432116491 )
IEEE Trans Pattern Anal Mach Intell - Automatic Relocalization and Loop Closing for Real-Time Monocular SLAM. ( 0,593946416741054 )
J Chem Inf Model - Efficient enumeration of stereoisomers of outerplanar chemical graphs using dynamic programming. ( 0,593383411032978 )
J. Comput. Biol. - An unbiased adaptive sampling algorithm for the exploration of RNA mutational landscapes under evolutionary pressure. ( 0,590631510394398 )
J. Comput. Biol. - Efficient error-correcting pooling designs constructed from pseudo-symplectic spaces over a finite field. ( 0,59001658934231 )
IEEE Trans Image Process - Unified structured learning for simultaneous human pose estimation and garment attribute classification. ( 0,589635107186749 )
IEEE Trans Pattern Anal Mach Intell - Free Energy Score Spaces: Using Generative Information in Discriminative Classifiers. ( 0,589240723600278 )
J Chem Inf Model - Generative topographic mapping-based classification models and their applicability domain: application to the biopharmaceutics Drug Disposition Classification System (BDDCS). ( 0,588709795734935 )
IEEE Trans Pattern Anal Mach Intell - Consistent Latent Position Estimation and Vertex Classification for Random Dot Product Graphs. ( 0,588413145205695 )
J Med Syst - Survival tree and MELD to predict long term survival in liver transplantation waiting list. ( 0,587855326838008 )
IEEE Trans Image Process - The Roadmaker's algorithm for the discrete pulse transform. ( 0,582412163778744 )
J Chem Inf Model - Mining for bioactive scaffolds with scaffold networks: improved compound set enrichment from primary screening data. ( 0,580415802471832 )
IEEE Trans Pattern Anal Mach Intell - Power Watershed: A Unifying Graph-Based Optimization Framework. ( 0,577827411405314 )
Comput Math Methods Med - The effect of edge definition of complex networks on protein structure identification. ( 0,57702904759703 )
J Chem Inf Model - Stereochemically consistent reaction mapping and identification of multiple reaction mechanisms through integer linear optimization. ( 0,575109742568423 )
J Chem Inf Model - Idealized models of protofilaments of human islet amyloid polypeptide. ( 0,570372887344827 )
IEEE Trans Image Process - An orientation inference framework for surface reconstruction from unorganized point clouds. ( 0,568320710462522 )
J. Comput. Biol. - A theoretical model for whole genome alignment. ( 0,567106192008512 )
IEEE Trans Pattern Anal Mach Intell - Shape Analysis of Elastic Curves in Euclidean Spaces. ( 0,566264544320488 )
J Chem Inf Model - Stereo signature molecular descriptor. ( 0,56583217584949 )
J Biomed Inform - SYFSA: a framework for systematic yet flexible systems analysis. ( 0,564285416231874 )
Comput Biol Chem - Quick path finding--quick algorithmic solution for unambiguous labeling of phylogenetic tree nodes. ( 0,564204890355238 )
Methods Inf Med - Quantitative score for the evaluation of kinematic recordings in neuropediatric diagnostics. Detection of complex patterns in spontaneous limb movements. ( 0,563203067660042 )
Int J Comput Assist Radiol Surg - Visualization support for the planning of hepatic needle placement. ( 0,562519124903927 )