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.