Sengupta Debarka, Pyne Aroonalok, Maulik Ujjwal, Bandyopadhyay Sanghamitra
Indian Statistical Institute, Kolkata.
IEEE/ACM Trans Comput Biol Bioinform. 2013 May-Jun;10(3):742-51. doi: 10.1109/TCBB.2013.74.
MicroRNAs are very recently discovered small noncoding RNAs, responsible for negative regulation of gene expression. Members of this endogenous family of small RNA molecules have been found implicated in many genetic disorders. Each microRNA targets tens to hundreds of genes. Experimental validation of target genes is a time- and cost-intensive procedure. Therefore, prediction of microRNA targets is a very important problem in computational biology. Though, dozens of target prediction algorithms have been reported in the past decade, they disagree significantly in terms of target gene ranking (based on predicted scores). Rank aggregation is often used to combine multiple target orderings suggested by different algorithms. This technique has been used in diverse fields including social choice theory, meta search in web, and most recently, in bioinformatics. Kemeny optimal aggregation (KOA) is considered the more profound objective for rank aggregation. The consensus ordering obtained through Kemeny optimal aggregation incurs minimum pairwise disagreement with the input orderings. Because of its computational intractability, heuristics are often formulated to obtain a near optimal consensus ranking. Unlike its real time use in meta search, there are a number of scenarios in bioinformatics (e.g., combining microRNA target rankings, combining disease-related gene rankings obtained from microarray experiments) where evolutionary approaches can be afforded with the ambition of better optimization. We conjecture that an ideal consensus ordering should have its total disagreement shared, as equally as possible, with the input orderings. This is also important to refrain the evolutionary processes from getting stuck to local extremes. In the current work, we reformulate Kemeny optimal aggregation while introducing a trade-off between the total pairwise disagreement and its distribution. A simulated annealing-based implementation of the proposed objective has been found effective in context of microRNA target ranking. Supplementary data and source code link are available at: >http://www.isical.ac.in/bioinfo_miu/ieee_tcbb_kemeny.rar.
微小RNA是最近才发现的一类小的非编码RNA，负责基因表达的负调控。这个内源性小RNA分子家族的成员已被发现与许多遗传疾病有关。每个微小RNA靶向数十到数百个基因。对靶基因进行实验验证是一个耗时且成本高昂的过程。因此，微小RNA靶标的预测是计算生物学中的一个非常重要的问题。尽管在过去十年中已经报道了几十种靶标预测算法，但它们在靶基因排名（基于预测分数）方面存在很大差异。排名聚合通常用于组合不同算法建议的多个目标排序。该技术已被应用于包括社会选择理论、网络元搜索以及最近的生物信息学等不同领域。凯梅尼最优聚合（KOA）被认为是排名聚合更深刻的目标。通过凯梅尼最优聚合获得的共识排序与输入排序的成对分歧最小。由于其计算上的难处理性，通常会制定启发式方法以获得接近最优的共识排名。与它在元搜索中的实时使用不同，在生物信息学中有许多情况（例如，组合微小RNA靶标排名、组合从微阵列实验获得的疾病相关基因排名），在这些情况下可以采用进化方法以实现更好的优化。我们推测，一个理想的共识排序应该将其总的分歧尽可能均匀地分配给输入排序。这对于防止进化过程陷入局部极值也很重要。在当前的工作中，我们重新制定了凯梅尼最优聚合，同时在成对分歧总量与其分布之间引入了权衡。已发现基于模拟退火的所提出目标的实现方法在微小RNA靶标排名的背景下是有效的。补充数据和源代码链接可在>http://www.isical.ac.in/bioinfo_miu/ieee_tcbb_kemeny.rar获取。
