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