{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,5]],"date-time":"2025-11-05T20:42:00Z","timestamp":1762375320016},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"1","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2009,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:sec>\n            <jats:title>Background<\/jats:title>\n            <jats:p>Network visualization would serve as a useful first step for analysis. However, current graph layout algorithms for biological pathways are insensitive to biologically important information, e.g. subcellular localization, biological node and graph attributes, or\/and not available for large scale networks, e.g. more than 10000 elements.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Results<\/jats:title>\n            <jats:p>To overcome these problems, we propose the use of a biologically important graph metric, betweenness, a measure of network flow. This metric is highly correlated with many biological phenomena such as lethality and clusters. We devise a new fast parallel algorithm calculating betweenness to minimize the preprocessing cost. Using this metric, we also invent a node and edge betweenness based fast layout algorithm (BFL). BFL places the high-betweenness nodes to optimal positions and allows the low-betweenness nodes to reach suboptimal positions. Furthermore, BFL reduces the runtime by combining a sequential insertion algorim with betweenness. For a graph with <jats:italic>n<\/jats:italic> nodes, this approach reduces the expected runtime of the algorithm to <jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic>\n              <jats:sup>2<\/jats:sup>) when considering edge crossings, and to <jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic> log <jats:italic>n<\/jats:italic>) when considering only density and edge lengths.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Conclusion<\/jats:title>\n            <jats:p>Our BFL algorithm is compared against fast graph layout algorithms and approaches requiring intensive optimizations. For gene networks, we show that our algorithm is faster than all layout algorithms tested while providing readability on par with intensive optimization algorithms. We achieve a 1.4 second runtime for a graph with 4000 nodes and 12000 edges on a standard desktop computer.<\/jats:p>\n          <\/jats:sec>","DOI":"10.1186\/1471-2105-10-19","type":"journal-article","created":{"date-parts":[[2009,1,15]],"date-time":"2009-01-15T19:14:06Z","timestamp":1232046846000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["BFL: a node and edge betweenness based fast layout algorithm for large scale networks"],"prefix":"10.1186","volume":"10","author":[{"given":"Tatsunori B","family":"Hashimoto","sequence":"first","affiliation":[]},{"given":"Masao","family":"Nagasaki","sequence":"additional","affiliation":[]},{"given":"Kaname","family":"Kojima","sequence":"additional","affiliation":[]},{"given":"Satoru","family":"Miyano","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,1,15]]},"reference":[{"issue":"5","key":"2749_CR1","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1016\/0925-7721(94)00014-X","volume":"4","author":"GD Battista","year":"1994","unstructured":"Battista GD, Eades P, Tamassia R, Tollis I: Algorithms for drawing graphs: an annotated bibliography. Computational Geometry: Theory and Applications. 1994, 4 (5): 235-282.","journal-title":"Computational Geometry: Theory and Applications"},{"key":"2749_CR2","first-page":"225","volume-title":"Proceedings of the Third International Conference on Bioinformatics and Genome Research","author":"PD Karp","year":"1994","unstructured":"Karp PD, Paley S: Automated Drawing of Metabolic Pathways. Proceedings of the Third International Conference on Bioinformatics and Genome Research. 1994, 225-238."},{"issue":"5","key":"2749_CR3","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1093\/bioinformatics\/17.5.461","volume":"17","author":"MY Becker","year":"2001","unstructured":"Becker MY, Rojas I: A graph layout algorithm for drawing metabolic pathways. Bioinformatics. 2001, 17 (5): 461-467. 10.1093\/bioinformatics\/17.5.461.","journal-title":"Bioinformatics"},{"key":"2749_CR4","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1109\/TSMC.1981.4308636","volume":"11","author":"K Sugiyama","year":"1981","unstructured":"Sugiyama K, Tagawa S, Toda M: Methods for visual understanding of hierarchical system structures. IEEE Transactions on Systems, Man and Cybernetics. 1981, 11: 109-125. 10.1109\/TSMC.1981.4308636.","journal-title":"IEEE Transactions on Systems, Man and Cybernetics"},{"key":"2749_CR5","volume-title":"Graph Drawing: Algorithms for the Visualization of Graphs","author":"GD Battista","year":"1998","unstructured":"Battista GD, Eades P, Tamassia R, Tollis IG: Graph Drawing: Algorithms for the Visualization of Graphs. 1998, Upper Saddle River, NJ: Prentice Hall PTR"},{"key":"2749_CR6","first-page":"149","volume":"42","author":"P Eades","year":"1984","unstructured":"Eades P: A heuristic for graph drawing. Congressus Numerantium. 1984, 42: 149-160.","journal-title":"Congressus Numerantium"},{"key":"2749_CR7","first-page":"442","volume-title":"Graph Drawing 2004","author":"U Dogrusoz","year":"2004","unstructured":"Dogrusoz U, Gral E, Cetintas A, Civril A, Demir E: A compound graph layout algorithm for biological pathways. Graph Drawing 2004. 2004, 442-447."},{"key":"2749_CR8","first-page":"314","volume-title":"Graph Drawing 2003","author":"B Genc","year":"2003","unstructured":"Genc B, Dogrusoz U: A constrained, force-directed layout algorithm for biological pathways. Graph Drawing 2003. 2003, 314-319."},{"issue":"9","key":"2749_CR9","doi-asserted-by":"publisher","first-page":"2036","DOI":"10.1093\/bioinformatics\/bti290","volume":"21","author":"W Li","year":"2005","unstructured":"Li W, Kurata H: A grid layout algorithm for automatic drawing of biochemical networks. Bioinformatics. 2005, 21 (9): 2036-2042. 10.1093\/bioinformatics\/bti290.","journal-title":"Bioinformatics"},{"key":"2749_CR10","doi-asserted-by":"crossref","unstructured":"Kojima K, Nagasaki M, Euna J, Miyano S: An efficient grid layout algorithm for biological networks utilizing various biological attributes. BMC Bioinformatics. 2007, 8 (76):","DOI":"10.1186\/1471-2105-8-76"},{"key":"2749_CR11","doi-asserted-by":"publisher","first-page":"3106","DOI":"10.1093\/bioinformatics\/btl533","volume":"22","author":"J Yoon","year":"2006","unstructured":"Yoon J, Blumer A, Lee K: An Algorithm for Modularity Analysis of Directed and Weighted Biological Networks Based on Edge-Betweenness Centrality. Bioinformatics. 2006, 22: 3106-3108. 10.1093\/bioinformatics\/btl533.","journal-title":"Bioinformatics"},{"key":"2749_CR12","first-page":"649","volume-title":"Proceedings of IEEE International Symposium on Circuits and Systems","author":"N Chiba","year":"1979","unstructured":"Chiba N, Nishioka I, Shirakawa I: An Algorithm of Maximal Planarization of Graphs. Proceedings of IEEE International Symposium on Circuits and Systems. 1979, Inesc ID \u2013 Lisboa, 649-652."},{"key":"2749_CR13","doi-asserted-by":"publisher","first-page":"1433","DOI":"10.1093\/bioinformatics\/btn196","volume":"24","author":"K Kojima","year":"2008","unstructured":"Kojima K, Nagasaki M, Miyano S: Fast grid layout algorithm for biological networks with sweep calculation. Bioinformatics. 2008, 24: 1433-41. 10.1093\/bioinformatics\/btn196.","journal-title":"Bioinformatics"},{"key":"2749_CR14","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/0378-8733(91)90017-N","volume":"13","author":"LC Freeman","year":"1991","unstructured":"Freeman LC, Borgatti SP, White DR: Centrality in valued graphs: A measure of betweenness based on network flow. Social Networks. 1991, 13: 141-154. 10.1016\/0378-8733(91)90017-N.","journal-title":"Social Networks"},{"key":"2749_CR15","doi-asserted-by":"publisher","first-page":"7821","DOI":"10.1073\/pnas.122653799","volume":"99","author":"M Girvan","year":"2002","unstructured":"Girvan M, Newman MEJ: Community structure in social and biological networks. PNAS. 2002, 99: 7821-7826. 10.1073\/pnas.122653799.","journal-title":"PNAS"},{"key":"2749_CR16","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1186\/1471-2105-6-39","volume":"6","author":"R Dunn","year":"2005","unstructured":"Dunn R, Dudbridge F, Sanderson CM: The Use of Edge-Betweenness Clustering to Investigate Biological Function in Protein Interaction Networks. BMC Bioinformatics. 2005, 6: 39-10.1186\/1471-2105-6-39.","journal-title":"BMC Bioinformatics"},{"key":"2749_CR17","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1080\/0022250X.2001.9990249","volume":"25","author":"U Brandes","year":"2001","unstructured":"Brandes U: A Faster Algorithm for Betweenness Centrality. Journal of Mathematical Soctology. 2001, 25: 163-177.","journal-title":"Journal of Mathematical Soctology"},{"key":"2749_CR18","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1155\/JBB.2005.96","volume":"2","author":"MP Joy","year":"2005","unstructured":"Joy MP, Brock A, Ingber DE, Huang S: High-Betweenness Proteins in the Yeast protein Interaction Network. Journal of Biomedicine and Biotechnology. 2005, 2: 96-103. 10.1155\/JBB.2005.96.","journal-title":"Journal of Biomedicine and Biotechnology"},{"key":"2749_CR19","first-page":"199","volume-title":"Proceedings German conference for bioinformatics","author":"D Koschutzki","year":"2004","unstructured":"Koschutzki D, Schreiber F: Comparison of Centrality for Biological Networks. Proceedings German conference for bioinformatics. Edited by: Stoye GJ. 2004, Bioinformatics Center Gatersleben-Halle, 199-206."},{"key":"2749_CR20","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1038\/35075138","volume":"411","author":"H Jeong","year":"2001","unstructured":"Jeong H, Mason SP, Barabasi AL, Oltvai ZN: Lethality and Centrality in Protein Networks. Nature. 2001, 411: 41-42. 10.1038\/35075138.","journal-title":"Nature"},{"key":"2749_CR21","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1093\/bioinformatics\/btl562","volume":"23","author":"F Luo","year":"2002","unstructured":"Luo F, Yang Y, Chen CF, Change R, Zhou J: Modular organization of protein interaction networks. Bioinformatics. 2002, 23: 207-214. 10.1093\/bioinformatics\/btl562.","journal-title":"Bioinformatics"},{"key":"2749_CR22","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1145\/234535.234538","volume":"15","author":"R Davidson","year":"1996","unstructured":"Davidson R, Harel D: Drawing Graphs Nicely Using Simulated Annealing. ACM Transactions on Graphics. 1996, 15: 301-331. 10.1145\/234535.234538.","journal-title":"ACM Transactions on Graphics"},{"key":"2749_CR23","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1145\/356924.356930","volume":"16","author":"H Samet","year":"1984","unstructured":"Samet H: The Quadtree and Related Heiarchical Data Structures. ACM Computing Surveys. 1984, 16: 187-260. 10.1145\/356924.356930.","journal-title":"ACM Computing Surveys"},{"key":"2749_CR24","volume-title":"Proceedings 6th International Symposium on Spatial Data Handling, University British Columbia","author":"D Andrews","year":"1994","unstructured":"Andrews D, Snoeyink J, Boritz J, Chan T, Denham G, Harrison J, Zhu C: Further comparisons of algorithms for geometric intersection problems. Proceedings 6th International Symposium on Spatial Data Handling, University British Columbia. 1994"},{"key":"2749_CR25","unstructured":"CSML webiste. [http:\/\/www.csml.org]"},{"key":"2749_CR26","first-page":"483","volume-title":"Proceeding of the 2004 International Conference on Information Networking","author":"AS Rodionov","year":"2004","unstructured":"Rodionov AS, Choo H: On Generating Random Network Structures: Connected Graphs. Proceeding of the 2004 International Conference on Information Networking. Edited by: Khang HK, Goto S. 2004, Inesc ID \u2013 Lisboa, 483-491."},{"key":"2749_CR27","doi-asserted-by":"publisher","first-page":"1595","DOI":"10.1126\/science.1133141","volume":"314","author":"ML Deque'ant","year":"2006","unstructured":"Deque'ant ML, Glynn E, Gaudenz K, Wahl M, Chen J, Mushegian A, Pourquie' O: A complex oscillating network of signaling genes underlies the mouse segmentation clock. Science. 2006, 314: 1595-1598. 10.1126\/science.1133141.","journal-title":"Science"},{"key":"2749_CR28","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1103\/RevModPhys.74.47","volume":"74","author":"R Albert","year":"2002","unstructured":"Albert R, Barabasi AL: Statistical mechanics of complex networks. Reviews of Modern Physics. 2002, 74: 47-97. 10.1103\/RevModPhys.74.47.","journal-title":"Reviews of Modern Physics"},{"key":"2749_CR29","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1016\/0020-0190(89)90102-6","volume":"31","author":"T Kamada","year":"1989","unstructured":"Kamada T, Kawai S: An algorithm for drawing general undirected graphs. Information Processing Letters. 1989, 31: 7-15. 10.1016\/0020-0190(89)90102-6.","journal-title":"Information Processing Letters"},{"key":"2749_CR30","doi-asserted-by":"publisher","first-page":"1129","DOI":"10.1002\/spe.4380211102","volume":"21","author":"TMJ Fruchterman","year":"1991","unstructured":"Fruchterman TMJ, Reingold EM: Graph drawing by force-directed placement. Software \u2013 Practice and Experience. 1991, 21: 1129-1164. 10.1002\/spe.4380211102.","journal-title":"Software \u2013 Practice and Experience"},{"key":"2749_CR31","first-page":"47","volume":"21","author":"V Batagelj","year":"1998","unstructured":"Batagelj V, Mrvar A: Pajek \u2013 program for large network analysis. Connections. 1998, 21: 47-57.","journal-title":"Connections"},{"key":"2749_CR32","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1007\/3-540-45848-4_34","volume":"2265","author":"A David","year":"2001","unstructured":"David A: Tulip. Lecture Notes Computer Science. 2001, 2265: 435-437.","journal-title":"Lecture Notes Computer Science"},{"key":"2749_CR33","doi-asserted-by":"publisher","first-page":"1882","DOI":"10.1093\/bioinformatics\/btg346","volume":"19","author":"K Han","year":"2003","unstructured":"Han K, Ju B: A fast layout algorithm for protein interaction networks. Bioinformatics. 2003, 19: 1882-1888. 10.1093\/bioinformatics\/btg346.","journal-title":"Bioinformatics"},{"key":"2749_CR34","first-page":"181","volume":"2","author":"M Nagasaki","year":"2003","unstructured":"Nagasaki M, Doi A, Matsuno H, Miyano S: Genomic Object Net: I. A platform for modeling and simulating biopathways. Applied Bioinformatics. 2003, 2: 181-184.","journal-title":"Applied Bioinformatics"},{"key":"2749_CR35","unstructured":"Cell Illustrator website. [http:\/\/www.cellillustrator.com]"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-10-19.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,31]],"date-time":"2021-08-31T21:32:56Z","timestamp":1630445576000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-10-19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,1,15]]},"references-count":35,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,12]]}},"alternative-id":["2749"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-10-19","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,1,15]]},"assertion":[{"value":"1 September 2008","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 January 2009","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 January 2009","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"19"}}