A Practical and Scalable Tool to Find Overlaps between Sequences

BioMed Research International - Tập 2015 - Trang 1-12 - 2015
Maan Haj Rachid1, Qutaibah M. Malluhi1
1KINDI Lab for Computing Research, Qatar University P.O. Box 2713, Doha, Qatar

Tóm tắt

The evolution of the next generation sequencing technology increases the demand for efficient solutions, in terms of space and time, for several bioinformatics problems. This paper presents a practical and easy-to-implement solution for one of these problems, namely, the all-pairs suffix-prefix problem, using a compact prefix tree. The paper demonstrates an efficient construction of this time-efficient and space-economical tree data structure. The paper presents techniques for parallel implementations of the proposed solution. Experimental evaluation indicates superior results in terms of space and time over existing solutions. Results also show that the proposed technique is highly scalable in a parallel execution environment.

Từ khóa


Tài liệu tham khảo

10.1016/0020-0190(92)90176-V

1997

10.1002/(sici)1097-024x(199911)29:13x0003C;1149::aid-spe274x003E;3.0.co;2-o

10.1016/s1570-8667(03)00065-0

10.1016/j.ipl.2009.10.015

10.1007/978-3-540-30213-1_23

10.1093/bioinformatics/btr321

10.1101/gr.126953.111

10.1186/1471-2105-13-82

10.1007/978-3-642-03784-9_7

10.1007/978-3-540-89097-3_17

10.1007/978-3-642-02008-7_9

10.1007/s00224-006-1198-x

10.1155/2014/745298

10.1145/301970.301973

Thông tin
Thông tin xuất bản

BioMed Research International

Tập 2015

1-12

Thông tin tác giả