Short read DNA fragment anchoring algorithm.
BACKGROUND
The emerging next-generation sequencing method based on PCR technology boosts genome sequencing speed considerably, the expense is also get decreased. It has been utilized to address a broad range of bioinformatics problems. Limited by reliable output sequence length of next-generation sequencing technologies, we are confined to study gene fragments with 30 - 50 bps in general and it is relatively shorter than traditional gene fragment length. Anchoring gene fragments in long reference sequence is an essential and prerequisite step for further assembly and analysis works. Due to the sheer number of fragments produced by next-generation sequencing technologies and the huge size of reference sequences, anchoring would rapidly becoming a computational bottleneck.


CONCLUSIONS
We compared algorithm efficiency on BLAT, SOAP and EMBF. The efficiency is defined as the count of total output results divided by time consumed to retrieve them. The data show that our algorithm EMBF have 3 - 4 times efficiency advantage over SOAP, and at least 150 times over BLAT. Moreover, when the reference sequence size is increased, the efficiency of SOAP will get degraded as far as 30%, while EMBF have preferable increasing tendency.


CONCLUSIONS
In conclusion, we deem that EMBF is more suitable for short fragment anchoring problem where result completeness and accuracy is predominant and the reference sequences are relatively large.
Wang
Wendi
W
Institute of Computing Technology, Chinese Academy of Sciences, Beijing, 100190, PR China. wangwendi@ncic.ac.cn
Zhang
Peiheng
P
Liu
Xinchun
X
D000465:Algorithms; D001483:Base Sequence; D019295:Computational Biology / Q000379:methods; D004247:DNA / Q000737:chemistry* / Q000235:genetics; D030541:Databases, Genetic; D015894:Genome, Human; D006801:Humans; D016415:Sequence Alignment / Q000379:methods; D017422:Sequence Analysis, DNA / Q000379:methods*
D004247:DNA