{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,6]],"date-time":"2026-10-06T14:56:37Z","timestamp":1791298597412,"version":"4.1.0"},"update-to":[{"DOI":"10.1371\/journal.pcbi.1011904","type":"new_version","label":"New version","source":"publisher","updated":{"date-parts":[[2024,3,1]],"date-time":"2024-03-01T00:00:00Z","timestamp":1709251200000}}],"reference-count":43,"publisher":"Public Library of Science (PLoS)","issue":"2","license":[{"start":{"date-parts":[[2024,2,20]],"date-time":"2024-02-20T00:00:00Z","timestamp":1708387200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"max-planck-society"}],"content-domain":{"domain":["www.ploscompbiol.org"],"crossmark-restriction":false},"short-container-title":["PLoS Comput Biol"],"abstract":"<jats:p>Volume electron microscopy together with computer-based image analysis are yielding neural circuit diagrams of ever larger regions of the brain. These datasets are usually represented in a cell-to-cell connectivity matrix and contain important information about prevalent circuit motifs allowing to directly test various theories on the computation in that brain structure. Of particular interest are the detection of cell assemblies and the quantification of feedback, which can profoundly change circuit properties. While the ordering of cells along the rows and columns doesn\u2019t change the connectivity, it can make special connectivity patterns recognizable. For example, ordering the cells along the flow of information, feedback and feedforward connections are segregated above and below the main matrix diagonal, respectively. Different algorithms are used to renumber matrices such as to minimize a given cost function, but either their performance becomes unsatisfying at a given size of the circuit or the CPU time needed to compute them scales in an unfavorable way with increasing number of neurons. Based on previous ideas, I describe an algorithm which is effective in matrix reordering with respect to both its performance as well as to its scaling in computing time. Rather than trying to reorder the matrix in discrete steps, the algorithm transiently relaxes the integer program by assigning a real-valued parameter to each cell describing its location on a continuous axis (\u2018smooth-index\u2019) and finds the parameter set that minimizes the cost. I find that the smooth-index algorithm outperforms all algorithms I compared it to, including those based on topological sorting.<\/jats:p>","DOI":"10.1371\/journal.pcbi.1011904","type":"journal-article","created":{"date-parts":[[2024,2,20]],"date-time":"2024-02-20T18:31:56Z","timestamp":1708453916000},"page":"e1011904","update-policy":"https:\/\/doi.org\/10.1371\/journal.pcbi.corrections_policy","source":"Crossref","is-referenced-by-count":4,"title":["Connectivity Matrix Seriation via Relaxation"],"prefix":"10.1371","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5537-8973","authenticated-orcid":true,"given":"Alexander","family":"Borst","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"340","published-online":{"date-parts":[[2024,2,20]]},"reference":[{"key":"pcbi.1011904.ref001","doi-asserted-by":"crossref","first-page":"1372","DOI":"10.1016\/j.cell.2020.08.010","article-title":"The mind of a mouse","volume":"182","author":"LF Abbott","year":"2020","journal-title":"Cell"},{"key":"pcbi.1011904.ref002","doi-asserted-by":"crossref","first-page":"483","DOI":"10.1038\/nmeth.2451","article-title":"From the connectome to brain function","volume":"10","author":"C Bargmann","year":"2013","journal-title":"Nature Methods"},{"key":"pcbi.1011904.ref003","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1038\/nature09818","article-title":"Wiring specificity in the direction-selectivity circuit of the retina","volume":"471","author":"KL Briggman","year":"2011","journal-title":"Nature"},{"key":"pcbi.1011904.ref004","doi-asserted-by":"crossref","first-page":"e329","DOI":"10.1371\/journal.pbio.0020329","article-title":"Serial block-face scanning electron microscopy to reconstruct three dimensional tissue nanostructure","volume":"2","author":"W Denk","year":"2004","journal-title":"PLoS Biol"},{"key":"pcbi.1011904.ref005","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1038\/nature12346","article-title":"Connectomic reconstruction of the inner plexiform layer in the mouse retina","volume":"500","author":"M Helmstaedter","year":"2013","journal-title":"Nature"},{"key":"pcbi.1011904.ref006","doi-asserted-by":"crossref","first-page":"618","DOI":"10.1126\/science.1209168","article-title":"The big and the small: challenges of imaging the brain\u2019s circuits","volume":"334","author":"JW Lichtman","year":"2011","journal-title":"Science"},{"key":"pcbi.1011904.ref007","doi-asserted-by":"crossref","first-page":"456","DOI":"10.1016\/j.cell.2015.09.029","article-title":"Reconstruction and simulation of neocortical microcircuitry","volume":"163","author":"H Markram","year":"2015","journal-title":"Cell"},{"key":"pcbi.1011904.ref008","doi-asserted-by":"crossref","first-page":"eaay3134","DOI":"10.1126\/science.aay3134","article-title":"Dense connectomic reconstruction in layer 4 of the somatosensory cortex","volume":"366","author":"A Motta","year":"2019","journal-title":"Science"},{"key":"pcbi.1011904.ref009","doi-asserted-by":"crossref","first-page":"e40025","DOI":"10.7554\/eLife.40025","article-title":"Comparisons between the ON- and OFF-edge motion pathways in the Drosophila brain","volume":"8","author":"K Shinomiya","year":"2019","journal-title":"Elife"},{"key":"pcbi.1011904.ref010","doi-asserted-by":"crossref","first-page":"e24394","DOI":"10.7554\/eLife.24394","article-title":"The comprehensive connectome of a neural substrate for \u2018ON\u2019 motion detection in Drosophila.","volume":"6","author":"SY Takemura","year":"2017","journal-title":"Elife"},{"key":"pcbi.1011904.ref011","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1038\/s41592-021-01330-0","article-title":"FlyWire: online community for whole-brain connectomics.","volume":"19","author":"S Dorkenwald","year":"2022","journal-title":"Nature Methods"},{"key":"pcbi.1011904.ref012","doi-asserted-by":"crossref","first-page":"1629","DOI":"10.1152\/jn.1993.70.4.1629","article-title":"Spatiotemporal firing patterns in the frontal cortex of behaving monkeys","volume":"70","author":"M Abeles","year":"1993","journal-title":"J Neurophysiol"},{"key":"pcbi.1011904.ref013","doi-asserted-by":"crossref","first-page":"529","DOI":"10.1038\/990101","article-title":"Stable propagation of synchronous firing in cortical neural networks","volume":"402","author":"M Diesmann","year":"1999","journal-title":"Nature"},{"key":"pcbi.1011904.ref014","volume-title":"Introduction to linear algebra","author":"G Strang","year":"2009","edition":"4"},{"key":"pcbi.1011904.ref015","volume-title":"Theoretical Neuroscience: Computational and Mathematical Modeling of Neural Systems.","author":"P Dayan","year":"2001"},{"key":"pcbi.1011904.ref016","article-title":"The eigenvalue value (in neuroscience).","author":"G Christodoulou","year":"2022","journal-title":"OSF Preprints"},{"key":"pcbi.1011904.ref017","doi-asserted-by":"crossref","first-page":"3599","DOI":"10.1523\/JNEUROSCI.2208-22.2023","article-title":"Connecting connectomes to physiology","volume":"43","author":"A Borst","year":"2023","journal-title":"J Neurosci"},{"key":"pcbi.1011904.ref018","doi-asserted-by":"crossref","first-page":"13339","DOI":"10.1073\/pnas.93.23.13339","article-title":"How the brain keeps the eyes still","volume":"93","author":"HS Seung","year":"1996","journal-title":"Proc Natl Acad Sci USA"},{"key":"pcbi.1011904.ref019","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1016\/S0896-6273(00)81155-1","article-title":"Stability of the memory of eye position in a recurrent network of conductance-based model neurons","volume":"26","author":"HS Seung","year":"2000","journal-title":"Neuron"},{"key":"pcbi.1011904.ref020","doi-asserted-by":"crossref","first-page":"550","DOI":"10.1037\/0033-295X.108.3.550","article-title":"The time course of perceptual choice: the leaky, competing accumulator model","volume":"108","author":"M Usher","year":"2001","journal-title":"Psychol Rev"},{"key":"pcbi.1011904.ref021","doi-asserted-by":"crossref","first-page":"579","DOI":"10.1007\/s00359-003-0431-1","article-title":"Desert ant navigation: how miniature brains solve complex tasks","volume":"189","author":"R Wehner","year":"2003","journal-title":"J Comp Physiol A"},{"key":"pcbi.1011904.ref022","doi-asserted-by":"crossref","first-page":"1965","DOI":"10.1126\/science.1126912","article-title":"The ant odometer: stepping on stilts and stumps","volume":"312","author":"M Wittlinger","year":"2006","journal-title":"Science"},{"key":"pcbi.1011904.ref023","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/s00359-019-01375-9","article-title":"How fly neurons compute the direction of visual motion","volume":"206","author":"A Borst","year":"2020","journal-title":"J Comp Physiol A"},{"key":"pcbi.1011904.ref024","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1146\/annurev-neuro-080422-111929","article-title":"How flies see motion","volume":"46","author":"A Borst","year":"2023","journal-title":"Ann Rev Neurosci"},{"key":"pcbi.1011904.ref025","doi-asserted-by":"crossref","unstructured":"Cuthill E, McKee J (1969) Reducing the bandwidth of sparse symmetric matrices. In: Proceedings of the 1969 24th National Conference, ACM \u201869, p. 157\u2013172, New York, NY, USA. Association for Computing Machinery.","DOI":"10.1145\/800195.805928"},{"key":"pcbi.1011904.ref026","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1137\/0201010","article-title":"Depth-first search and linear graph algorithms","volume":"1","author":"RE Tarjan","year":"1972","journal-title":"SIAM J. Comput"},{"key":"pcbi.1011904.ref027","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1016\/S0022-0000(74)80049-8","article-title":"Testing flow graph reducibility","volume":"9","author":"RE Tarjan","year":"1974","journal-title":"J. Comput. Syst. Sci"},{"key":"pcbi.1011904.ref028","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1016\/0020-0190(93)90079-O","article-title":"A fast and effective heuristic for the feedback arc set problem","volume":"47","author":"P Eades","year":"1993","journal-title":"Information Processing Letters"},{"key":"pcbi.1011904.ref029","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/0020-0190(94)00086-7","article-title":"Approximations for the maximum acyclic subgraph problem","volume":"51","author":"R Hassin","year":"1994","journal-title":"Information Processing Letters"},{"key":"pcbi.1011904.ref030","volume-title":"Sorting heuristics for the feedback arc set problem","author":"FJ Brandenburg","year":"2011"},{"issue":"1","key":"pcbi.1011904.ref031","article-title":"An exact method for the minimum feedback arc set problem","volume":"26","author":"A Baharev","year":"2021","journal-title":"ACM J of experimental algorithms"},{"key":"pcbi.1011904.ref032","article-title":"Computing a feedback arc set using pagerank.","author":"V Geladaris","year":"2022","journal-title":"arXiv:2208.09234v2"},{"key":"pcbi.1011904.ref033","unstructured":"Page L, Brin S, Motwani R, Winograd T (1999) The page-rank citation ranking: Bringing order to the web. Technical Report 1999\u201366, Stanford InfoLab Previous number = SIDL-WP-1999-0120."},{"key":"pcbi.1011904.ref034","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1002\/sam.10071","article-title":"Seriation and matrix reordering methods: An historical overview","volume":"3","author":"I Liiv","year":"2010","journal-title":"Stat. Anal. Data Min"},{"key":"pcbi.1011904.ref035","doi-asserted-by":"crossref","first-page":"693","DOI":"10.1111\/cgf.12935","article-title":"Matrix reordering methods for table and network visualization","volume":"35","author":"M Behrisch","year":"2016","journal-title":"Computer Graphics Forum"},{"key":"pcbi.1011904.ref036","doi-asserted-by":"crossref","first-page":"364","DOI":"10.1007\/3-540-58950-3_391","article-title":"A simple and unified method for drawing graphs: Magnetic-spring algorithm","author":"K Sugiyama","year":"1995","journal-title":"Proc Graph Drawing (GD \u201894)"},{"key":"pcbi.1011904.ref037","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1109\/TVCG.2004.1260757","article-title":"Combining hierarchy and energy for drawing directed graphs","volume":"10","author":"L Carmel","year":"2004","journal-title":"IEEE Trans. Vis Comput Graph"},{"key":"pcbi.1011904.ref038","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/j.neuron.2009.03.020","article-title":"Reading the book of memory: sparse sampling versus dense mapping of connectomes","volume":"62","author":"HS Seung","year":"2009","journal-title":"Neuron"},{"key":"pcbi.1011904.ref039","article-title":"Convex relaxations for permutation problems","volume":"26","author":"F Vogel","year":"2013","journal-title":"Advances in Neural Information Processing Systems (NIPS)"},{"key":"pcbi.1011904.ref040","article-title":"Fast approximate quadratic programming for graph matching","author":"JT Vogelstein","journal-title":"PLoS ONE"},{"key":"pcbi.1011904.ref041","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1038\/s41592-019-0686-2","article-title":"SciPy 1.0: Fundamental algorithms for scientific computing in python","volume":"17","author":"P Virtanen","year":"2020","journal-title":"Nature Methods"},{"key":"pcbi.1011904.ref042","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1016\/0022-0000(80)90046-X","article-title":"Structure preserving reductions among convex optimization problems","volume":"21","author":"G Ausiello","year":"1980","journal-title":"J Computer System Sciences"},{"key":"pcbi.1011904.ref043","doi-asserted-by":"crossref","first-page":"e66018","DOI":"10.7554\/eLife.66018","article-title":"Information flow, cell types and stereotypy in a full olfactory connectome.","volume":"10","author":"P Schlegel","year":"2021","journal-title":"eLife"}],"updated-by":[{"DOI":"10.1371\/journal.pcbi.1011904","type":"new_version","label":"New version","source":"publisher","updated":{"date-parts":[[2024,3,1]],"date-time":"2024-03-01T00:00:00Z","timestamp":1709251200000}}],"container-title":["PLOS Computational Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dx.plos.org\/10.1371\/journal.pcbi.1011904","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,1]],"date-time":"2024-03-01T18:48:04Z","timestamp":1709318884000},"score":1,"resource":{"primary":{"URL":"https:\/\/dx.plos.org\/10.1371\/journal.pcbi.1011904"}},"subtitle":[],"editor":[{"given":"Matthieu","family":"Louis","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"editor"}]}],"short-title":[],"issued":{"date-parts":[[2024,2,20]]},"references-count":43,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2024,2,20]]}},"URL":"https:\/\/doi.org\/10.1371\/journal.pcbi.1011904","relation":{"new_version":[{"id-type":"doi","id":"10.1371\/journal.pcbi.1011904","asserted-by":"object"}]},"ISSN":["1553-7358"],"issn-type":[{"value":"1553-7358","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,2,20]]}}}