Searching and Indexing Circular Patterns

TY - CHAP

T1 - Searching and Indexing Circular Patterns

AU - Iliopoulos, Costas S.

AU - Pissis, Solon P.

AU - Rahman, M. Sohel

PY - 2017

Y1 - 2017

N2 - Circular DNA sequences can be found in viruses, as plasmids in archaea and bacteria, and in the mitochondria and plastids of eukaryotic cells. Hence, circular sequence comparison finds applications in several biological contexts (Barton et al., Experimental algorithms. Lecture notes in computer science, vol 9125, pp 247--258, 2015; Barton et al., Algorithms Mol Biol 9(9):2014; Uliel et al., Protein Eng 14(8):533--542, 2001). This motivates the design of efficient algorithms (Barton et al., Language and automata theory and applications. Lecture notes in computer science, vol 8977, pp 85--96. Springer, Berlin, 2015) and data structures (Hon et al., Combinatorial pattern matching. Lecture notes in computer science, vol 7922, pp 142--152. Springer, Berlin/Heidelberg, 2013) that are devoted to the specific comparison of circular sequences, as they can be relevant in the analysis of organisms with such structure (Grossi et al., Proceedings of algorithms in bioinformatics - 15th international workshop, WABI 2015, Atlanta, GA, Sept 10--12, 2015. Lecture notes in computer science, vol 9289, pp 203--216. Springer, Berlin, 2015; Gusfield, Algorithms on strings, trees, and sequences - computer science and computational biology. Cambridge University Press, Cambridge, 1997).

AB - Circular DNA sequences can be found in viruses, as plasmids in archaea and bacteria, and in the mitochondria and plastids of eukaryotic cells. Hence, circular sequence comparison finds applications in several biological contexts (Barton et al., Experimental algorithms. Lecture notes in computer science, vol 9125, pp 247--258, 2015; Barton et al., Algorithms Mol Biol 9(9):2014; Uliel et al., Protein Eng 14(8):533--542, 2001). This motivates the design of efficient algorithms (Barton et al., Language and automata theory and applications. Lecture notes in computer science, vol 8977, pp 85--96. Springer, Berlin, 2015) and data structures (Hon et al., Combinatorial pattern matching. Lecture notes in computer science, vol 7922, pp 142--152. Springer, Berlin/Heidelberg, 2013) that are devoted to the specific comparison of circular sequences, as they can be relevant in the analysis of organisms with such structure (Grossi et al., Proceedings of algorithms in bioinformatics - 15th international workshop, WABI 2015, Atlanta, GA, Sept 10--12, 2015. Lecture notes in computer science, vol 9289, pp 203--216. Springer, Berlin, 2015; Gusfield, Algorithms on strings, trees, and sequences - computer science and computational biology. Cambridge University Press, Cambridge, 1997).

U2 - 10.1007/978-3-319-59826-0_3

DO - 10.1007/978-3-319-59826-0_3

M3 - Chapter

SN - 978-3-319-59826-0

SP - 77

EP - 90

BT - Algorithms for Next-Generation Sequencing Data: Techniques, Approaches, and Applications

A2 - Elloumi, Mourad

PB - Springer International Publishing Switzerland

CY - Cham

ER -