An Almost Quadratic Time Algorithm for Sparse Spliced Alignment
An Almost Quadratic Time Algorithm for Sparse Spliced Alignment
复制标题
一种稀疏拼接对齐的近二次时间算法
DOI：
10.1007/s00224-009-9239-x
复制
发表时间：
2009
影响因子：
0.5
通讯作者：
Y. Sakai
中科院分区：
文献类型：
--
作者：
Y. Sakai
稀疏拼接比对问题是从一个长度为O（n）的DNA序列的O（n）个指定的候选外显子中找到一个由零个或多个外显子组成的链，该序列与一个长度为n的已知相关基因序列最相似。本文通过提出一个O（n2logn）时间算法，改进了目前已知的最快的算法的运行时间，该算法的执行时间为O（n2.25）时间，或者最近的时间为O（n2log2n）时间。
The sparse spliced alignment problem consists of finding a chain of zero or more exons fromO(n) prescribed candidate exons of a DNA sequence of lengthO(n) that is most similar to a known related gene sequence of lengthn. This study improves the running time of the fastest known algorithm for this problem to date, which executes inO(n2.25) time, or very recently, inO(n2log2n) time, by proposing anO(n2logn)-time algorithm.
DOI：
--
发表时间：
2016
期刊：
影响因子：
--
作者：
Shuhei Denzumi
通讯作者：
Shuhei Denzumi