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

AF：小：用于局部和多目标生物网络比对的多尺度光谱特征

• 批准号: 1319998
• 负责人: Carleton Kingsford
• 金额: $ 48万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-09-01 至 2017-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1319998&HistoricalAwards=false
• 关键词: AF; Small; Multiscale; Spectral; Signatures

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.

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