AF: Small: Multiscale Spectral Signatures for Local and Multi-objective Biological Network Alignment

在许多环境中，有成百上千个微生物物种在一个群落中相互作用。这些群落可以从元基因组测序项目中确定，在该项目中，从环境(海水样本、一块土壤等)收集DNA。群落可以用生态网络表示，其中节点对应于物种，边缘表示微生物之间的推断或已知关系(竞争、共生等)。然后，可以通过比较它们的网络来比较不同环境中或随时间变化的微生物群落。这种比较的一种计算方法是通过寻找局部相似区域来比对网络，这是网络比对的一种新应用。然而，网络比对是一个具有计算挑战性的问题，目前还没有算法具有足够的速度、精度和通用性。本项目将开发网络比对的改进算法，以比较微生物生态网络和计算生物学中的其他应用。网络比对在计算生物学中被广泛采用来比较生物路径，纠正网络中的错误，并形成关于具有未知功能的基因的角色的假设。智力价值不同环境或时间点的网络之间的改进排列将有助于识别保守的相互作用模式，微生物之间的真正功能关系，以及在不同微生物群落中执行类似功能的细菌。该项目开发的算法还将导致对蛋白质功能和蛋白质相互作用的更准确预测。该项目所采取的方法将使用两个主要的算法创新，这将导致更有用的局部网络校准器。第一个是开发了一种新的签名，用于基于网络节点的连接和属性以及附近其他节点的连接和属性来描述网络节点之间的相似性。该签名基于表示每个节点周围的网络区域的子图的特征值。初步工作表明，这种多尺度光谱签名产生的全球网络比对比使用其他方法的网络比对更准确、更有效。该项目的第二个主要算法创新是将网络对齐显式建模为一个多目标优化问题。这将允许新的比对者处理经常竞争的比对要求，这样他们就可以找到例如具有相似序列和相似相互作用伙伴的基因的网络区域。这些创新将带来更准确、更高质量的比对，产生新的生物学见解。广泛影响该项目有三个方面。将开发一款教育平板电脑应用程序，向高中生教授图论。这个交互式应用程序将向一群通常没有机会学习它的学生介绍一个美丽、平易近人但又复杂的数学分支。此外，项目人员将参加卡内基梅隆大学的项目，旨在通过展示新技术向中学女孩介绍技术主题。最后，虽然重点放在生物应用上，但作为该项目的一部分开发的技术和软件预计将在图形和视觉应用中有用，例如照片中的物体识别。

Within many environments, there are hundreds or thousands of microbial species that interact in a community. These communities can be determined from metagenomic sequencing projects in which DNA is collected from an environment (a sample of seawater, a patch of soil, etc.). The communities can be represented using ecological networks where nodes correspond to species and edges represent inferred or known relationships between the microbes (competition, symbiosis, etc.). Microbial communities in different environments or over time can then be compared by comparing their networks. One computational approach for this comparison is to align the networks by finding regions of local similarity, a new application of network alignment. However, network alignment is a computationally challenging problem for which there are no algorithms that have sufficient speed, accuracy, and generality.This project will develop improved algorithms for network alignment to compare microbial ecological networks and for other applications in computational biology. Network alignment has found wide adoption in computational biology to compare biological pathways, to correct errors in networks, and to form hypotheses about the roles of genes with unknown function. Intellectual MeritImproved alignments between networks for different environments or time points will help identify conserved patterns of interactions, truly functional relationships between microbes, and bacteria that are performing similar functions within different microbial communities. The algorithms developed by this project will also lead to more accurate prediction of protein function and protein interactions.The approach taken by the project will use two primary algorithmic innovations, which will lead to substantially more useful local network aligners. The first is the development of a new signature for describing the similarities between network nodes based on their connections and attributes and the connections and attributes of other nearby nodes. This signature is based on the eigenvalues of subgraphs representing regions of the network around each node. Preliminary work has shown that such a multiscale spectral signature results in global network alignments that are more accurate, and more efficiently computed, than those using other approaches. The second main algorithmic innovation for this project is the explicit modeling of network alignment as an optimization problem with multiple objectives. This will allow the new aligners to handle the often-competing requirements on alignments so that they can find regions of networks that have, for example, genes with similar sequences and similar interaction partners. These innovations will lead to more accurate, high-quality alignments yielding new biological insight.Broader ImpactThis project has three aspects to its broader impact. An educational tablet application will be developed that will teach graph theory to high-school students. This interactive application will introduce a beautiful, approachable, yet sophisticated, branch of mathematics to a group of students who often would not have the chance to study it. In addition, the project personnel will participate in programs at Carnegie Mellon University that aim to introduce middle-school girls to technical topics by presenting the new techniques. Finally, while the focus is on biological applications, the techniques and software developed as part of this project are expected to be useful in graphics and vision applications, such as object recognition in photos.