A Chaining Algorithm for Mapping cDNA Sequences to Multiple Genomic Sequences
DOI: 10.1007/978-3-540-75530-2_1
关键词: Sequence (medicine) 、 Chain (algebraic topology) 、 Multiple sequence alignment 、 Set (abstract data type) 、 Chaining 、 Computer science 、 Algorithm 、 Graph based 、 Complementary DNA
摘要: Given a set of matches between cDNA sequence and multiple genomic sequences, we present subquadratic chaining algorithm for computing an optimal chain colinear matches, while allowing overlaps the matches. Our improves upon quadratic graph based solution, extends previous algorithms which are limited to single sequence. The resulting serve as anchors alignment given sequences.
springer.com
springerlink.com参考文章(19)
Enno Ohlebusch, Mohamed I. Abouelhoda, Chaining Algorithms and Applications in Comparative Genomics ,(2004)
Srinivas Aluru, Handbook Of Computational Molecular Biology ,(2010)
Jitender S. Deogun, Jingyi Yang, Fangrui Ma, EMAGEN: an efficient approach to multiple whole genome alignment asia pacific bioinformatics conference. pp. 113- 122 ,(2004)
Tetsuo Shibuya, Igor Kurochkin, Match Chaining Algorithms for cDNA Mapping Lecture Notes in Computer Science. pp. 462- 475 ,(2003) , 10.1007/978-3-540-39763-2_33
WEBB MILLER, MARK BOGUSKI, BALAJI RAGHAVACHARI, ZHENG ZHANG, ROSS C. HARDISON, Constructing aligned sequence blocks. Journal of Computational Biology. ,vol. 1, pp. 51- 64 ,(1994) , 10.1089/CMB.1994.1.51
David Eppstein, Zvi Galil, Raffaele Giancarlo, Giuseppe F. Italiano, Sparse dynamic programming I Journal of the ACM. ,vol. 39, pp. 519- 545 ,(1992) , 10.1145/146637.146650
ZHENG ZHANG, BALAJI RAGHAVACHARI, ROSS C. HARDISON, WEBB MILLER, Chaining multiple-alignment blocks. Journal of Computational Biology. ,vol. 1, pp. 217- 226 ,(1994) , 10.1089/CMB.1994.1.217
Webb Miller, Gene Myers, Chaining multiple-alignment fragments in sub-quadratic time symposium on discrete algorithms. pp. 38- 47 ,(1995) , 10.5555/313651.313661
Mohamed Ibrahim Abouelhoda, Enno Ohlebusch, Chaining algorithms for multiple genome comparison Journal of Discrete Algorithms. ,vol. 3, pp. 321- 341 ,(2005) , 10.1016/J.JDA.2004.08.011
Enno Ohlebusch, Stefan Kurtz, Space efficient computation of rare maximal exact matches between multiple sequences. Journal of Computational Biology. ,vol. 15, pp. 357- 377 ,(2008) , 10.1089/CMB.2007.0105