高通量数据的生物信息学分析和一致性排序算法研究

摘要

在后基因组时代，利用生物信息学方法解决生物学问题越来越受到人们的重视。本论文主要研究生物学高通量数据的生物信息学分析，和一致性排序算法的开发。 在分子生物学和遗传学中，我们把发生在新生前体信使RNA转录本上的内含子移除同时外显子连接在一起的过程叫做RNA剪接。在这一过程中研究者们对U2AF异源二聚体，在前体信使RNA剪接过程中识别定义功能性的3'剪接位点的作用已经有很好的研究。但是依然有许多重要的问题不清楚，其中就包括最近在它们基因上刚发现的癌症相关的高频率突变位点是否有功能性作用。通过基因组范围的U2AF和RNA相互作用分析，我们发现在人类基因组中，U2AF能识别定义约88％的功能性3'剪接位点。同时在基因组其它位置也有大量的U2AF结合事件。通过全基因组数据分析和单基因实验验证，我们发现U2AF在内含子中的结合会抑制紧接着的下游3'剪接位点的剪接。在盒式外显子可变剪接事件中这表现为:U2AF结合在可变外显子上游会抑制可变外显子的剪接;U2AF结合在可变外显子下游会抑制下游组成型外显子的剪接进而促进与之竞争的可变外显子的剪接。基于我们的高质量高通量测序数据，利用最大熵机器学习方法，我们进一步建立一个U2AF65结合序列打分模型，可以用来预测U2AF65结合位点。用这一打分模型同样验证了我们前面提出的U2AF调控模型。这些发现揭示了U2AF在基因组范围的功能和调控机制，有助于我们进一步研究其相关疾病。 人们越来越意识到在大数据时代，对生物学数据排序很重要。然而对同一个问题，基于不同的数据和排序方法，通常会有很多不同的排序结果。Cohen-Boulakia研究组提出从这些不同的排序结果中生成一个一致性的排序。这样既可以突出这些不同排序结果中的相同的信息，同时可以最小化它们之间不一致的部分。所以这一方法可以有效的减少生物学数据中的噪声和错误。然而基于Kendall-tau距离，即使只有4不同的排序，生成一致性排序问题仍然是个NP难问题。在本文中，我们提出了一种新的Pivot算法，叫Consistent-Pivot算法。该算法采用了一种新的支点选择和其它元素分配方法。我们认为这一算法充分利用了一致性排序问题的数据特点。实验证明不论在运行时间还是准确度上，Consistent-Pivot算法都优于之前的Pivot算法。

目录

声明

Content

摘要

Abstract

Chapter 1：Introduction

Chapter 2：Genome-wide Analysis of U2AF Functions in pre-mRNA Splicing

2．1 Introduction

2．1．1 RNA splicing

2．1．2 Alternative splicing

2．1．3 Splicing regulation

2．1．4 Splicing and disease

2．1．5 Motivation

2．2 Methods

2．2．1 High throughput sequencing

2．2．2 Bioinformatics analysis

2．3 Results

2．3．1 Genome-wide mapping of U2AF-RNA interactions

2．3．2 U2AF recognition of～88％ functional 3’splice sites in the human genome

2．3．3 Additional U2AF binding events beyond functional 3’splice sites

2．3．4 Critical roles of U2AF in regulated splicing

2．3．5 Multiple mechanisms underlying U2AF－regulated alternative splicing

2．3．6 Polar effect of U2AF65 binding on downstream 3’splice site recognition

2．3．7 Coordinated action of U2AF65 and U2AF35 in regulated splicing

2．3．8 U2AF65 binding scores

2．4 Discussion

Chapter 3：Consistent-Pivot：A New effective Pivot Algorithms for Ranking Aggregation Problem

3．1 Introduction

3．2 Notations

3．2．1 Ranking with ties

3．2．2 Unifying a set of partial rankings

3．2．3 Distance measures

3．2．4 Kemeny optimal aggregations

3．3 Previous algorithms

3．3．1 Some heuristics and approximation algorithms

3．3．2 Other algorithms

3．3．3 Pivot Algorithms

3．4 Methods

3．4．1 Consistent-Pivot algorithm

3．4．2 Experiments on the algorithms

3．5 Results

3．5．1 Results on real biological data

3．5．2 Results on WebSearch data

3．5．3 Results on synthetic data

3．6 Discussion

Reference

Appendix

Acknowledgement