John A. Paulson School of Engineering and Applied Sciences, Harvard University, Cambridge, MA, USA.
Computer Science Laboratory, SRI International, Washington, DC, USA.
Sci Rep. 2022 Jul 5;12(1):11349. doi: 10.1038/s41598-022-15027-7.
Following significant advances in image acquisition, synapse detection, and neuronal segmentation in connectomics, researchers have extracted an increasingly diverse set of wiring diagrams from brain tissue. Neuroscientists frequently represent these wiring diagrams as graphs with nodes corresponding to a single neuron and edges indicating synaptic connectivity. The edges can contain "colors" or "labels", indicating excitatory versus inhibitory connections, among other things. By representing the wiring diagram as a graph, we can begin to identify motifs, the frequently occurring subgraphs that correspond to specific biological functions. Most analyses on these wiring diagrams have focused on hypothesized motifs-those we expect to find. However, one of the goals of connectomics is to identify biologically-significant motifs that we did not previously hypothesize. To identify these structures, we need large-scale subgraph enumeration to find the frequencies of all unique motifs. Exact subgraph enumeration is a computationally expensive task, particularly in the edge-dense wiring diagrams. Furthermore, most existing methods do not differentiate between types of edges which can significantly affect the function of a motif. We propose a parallel, general-purpose subgraph enumeration strategy to count motifs in the connectome. Next, we introduce a divide-and-conquer community-based subgraph enumeration strategy that allows for enumeration per brain region. Lastly, we allow for differentiation of edges by types to better reflect the underlying biological properties of the graph. We demonstrate our results on eleven connectomes and publish for future analyses extensive overviews for the 26 trillion subgraphs enumerated that required approximately 9.25 years of computation time.
在连接组学领域，图像采集、突触检测和神经元分割技术取得了重大进展，研究人员已经从脑组织中提取出越来越多样化的连接图。神经科学家经常将这些连接图表示为节点对应单个神经元、边表示突触连接的图。边可以包含“颜色”或“标签”，以表示兴奋性连接与抑制性连接等。通过将连接图表示为图，我们可以开始识别模式，即对应特定生物学功能的常见子图。大多数关于这些连接图的分析都集中在假设的模式上，即我们预期找到的模式。然而，连接组学的目标之一是识别以前没有假设过的具有生物学意义的模式。为了识别这些结构，我们需要进行大规模子图枚举以找到所有独特模式的频率。精确的子图枚举是一项计算成本很高的任务，尤其是在边密集的连接图中。此外，大多数现有的方法都没有区分边的类型，这会显著影响模式的功能。我们提出了一种并行的、通用的子图枚举策略来计算连接组中的模式。接下来，我们引入了一种基于划分和合并的社区子图枚举策略，允许按大脑区域进行枚举。最后，我们允许按边的类型进行区分，以更好地反映图的潜在生物学特性。我们在十一个连接组上展示了我们的结果，并发布了用于未来分析的 26 万亿个子图的详细概述，枚举这些子图大约需要 9.25 年的计算时间。
