A Common Framework for Linear and Cyclic Multiple Sequence Alignment Problems

详细信息    查看全文

• 作者：Sebastian Will (20)
  Peter F. Stadler (20) (21) (22) (23) (24) (25) (26)
  
• 关键词：cyclic sequence alignment ; multiple sequence alignment ; cyclic orders ; integer linear programming ; circular RNAs
• 刊名：Lecture Notes in Computer Science
• 出版年：2014
• 出版时间：2014
• 年：2014
• 卷：8701
• 期：1
• 页码：135-147
• 全文大小：248 KB
• 参考文献：1. Jeck, W.R., Sharpless, N.E.: Detecting and characterizing circular RNAs. Nat. Biotechnol.聽32, 453鈥?61 (2014) CrossRef
  2. Danan, M., Schwartz, S., Edelheit, S., Sorek, R.: Transcriptome-wide discovery of circular RNAs in Archaea. Nucleic Acids Res.聽40, 3131鈥?142 (2012) CrossRef
  3. Ding, B.: Viroids: self-replicating, mobile, and fast-evolving noncoding regulatory RNAs. Wiley Interdiscip Rev. RNA聽1, 362鈥?75 (2010) CrossRef
  4. Doose, G., Alexis, M., Kirsch, R., Findei脽, S., Langenberger, D., Machn茅, R., M枚rl, M., Hoffmann, S., Stadler, P.F.: Mapping the RNA-seq trash bin: Unusual transcripts in prokaryotic transcriptome sequencing data. RNA Biology聽10, 1204鈥?210 (2013) CrossRef
  5. Bunke, H., B眉hler, U.: Applications of approximate string matching to 2D shape recognition. Patt. Recogn.聽26, 1797鈥?812 (1993) CrossRef
  6. Gregor, J., Thomason, M.G.: Dynamic programming alignment of sequences representing cyclic patterns. IEEE Trans. Patt. Anal. Mach. Intell.聽15, 129鈥?35 (1993) CrossRef
  7. Maes, M.: On a cyclic string-to-string correction problem. Inform. Process. Lett.聽35, 73鈥?8 (1990) CrossRef
  8. Mollineda, R.A., Vidal, E., Casacuberta, F.: Cyclic sequence alignments: approximate versus optimal techniques. Int. J. Pattern Rec. Artif. Intel.聽16, 291鈥?99 (2002) CrossRef
  9. Dewey, T.G.: A sequence alignment algorithm with an arbitrary gap penalty function. J. Comp. Biol.聽8, 177鈥?90 (2001) CrossRef
  10. Benson, G.: Tandem cyclic alignment. Discrete Appl. Math.聽146, 124鈥?33 (2005) CrossRef
  11. Mosig, A., Hofacker, I.L., Stadler, P.F.: Comparative analysis of cyclic sequences: Viroids and other small circular RNAs. In: Giegerich, R., Stoye, J. (eds.) Proceedings GCB 2006, vol. P-83. Lecture Notes in Informatics, pp. 93鈥?02 (2006)
  12. Wang, L., Jiang, T.: On the complexity of multiple sequence alignment. J. Comput. Biol.聽1, 337鈥?48 (1994) CrossRef
  13. Just, W.: Computational complexity of multiple sequence alignment with SP-score. J. Comput. Biol.聽8, 615鈥?23 (2001) CrossRef
  14. Elias, I.: Settling the intractability of multiple alignment. J. Comput. Biol.聽13, 1323鈥?339 (2006) CrossRef
  15. Morgenstern, B., Frech, K., Dress, A., Werner, T.: DIALIGN: finding local similarities by multiple sequence alignment. Bioinformatics聽14(3), 290鈥?94 (1998) CrossRef
  16. Morgenstern, B., Stoye, J., Dress, A.W.M.: Consistent equivalence relations: a set-theoretical framework for multiple sequence alignments. Technical report, University of Bielefeld, FSPM (1999)
  17. Otto, W., Stadler, P.F., Prohaska, S.J.: Phylogenetic footprinting and consistent sets of local aligments. In: Giancarlo, R., Manzini, G. (eds.) CPM 2011. LNCS, vol.聽6661, pp. 118鈥?31. Springer, Heidelberg (2011) CrossRef
  18. Meggido, N.: Partial and complete cyclic orders. Bull. Am. Math. Soc.聽82, 274鈥?76 (1976) CrossRef
  19. Galil, Z., Megiddo, N.: Cyclic ordering in NP-complete. Theor. Comp. Sci.聽5, 179鈥?82 (1977) CrossRef
  20. Nov谩k, V.: Cuts in cyclically ordered sets. Czech. Math. J.聽34, 322鈥?33 (1984)
  21. Reinert, K., Lenhof, H.P., Mutzel, P., Mehlhorn, K., Kececioglu, J.D.: A branch-and-cut algorithm for multiple sequence alignment. In: Proceedings of the First Annual International Conference on Research in Computational Molecular Biology (RECOMB), pp. 241鈥?50. ACM (1997)
  22. Lenhof, H.P., Morgenstern, B., Reinert, K.: An exact solution for the segment-to-segment multiple sequence alignment problem. Bioinformatics聽15, 203鈥?10 (1999) CrossRef
  23. Hofacker, I.L., Bernhart, S.H., Stadler, P.F.: Alignment of RNA base pairing probability matrices. Bioinformatics聽20, 2222鈥?227 (2004) CrossRef
  24. Will, S., Reiche, K., Hofacker, I.L., Stadler, P.F., Backofen, R.: Inferring non-coding RNA families and classes by means of genome-scale structure-based clustering. PLoS Comput. Biol.聽3, e65 (2007)
  25. Bauer, M., Klau, G.W., Reinert, K.: Accurate multiple sequence-structure alignment of RNA sequences using combinatorial optimization. BMC Bioinformatics 8 (2007)
  26. M枚hl, M., Will, S., Backofen, R.: Lifting prediction to alignment of RNA pseudoknots. J. Comp. Biol.聽17, 429鈥?42 (2010) CrossRef
  
• 作者单位：Sebastian Will (20)
  Peter F. Stadler (20) (21) (22) (23) (24) (25) (26)
  
  20. Dept. Computer Science, and Interdisciplinary Center for Bioinformatics, Univ. Leipzig, H盲rtelstr. 16-18, Leipzig, Germany
  21. MPI Mathematics in the Sciences, Inselstr. 22, Leipzig, Germany
  22. FHI Cell Therapy and Immunology, Perlickstr. 1, Leipzig, Germany
  23. Dept. Theoretical Chemistry, Univ. Vienna, W盲hringerstr. 17, Wien, Austria
  24. Bioinformatics and Computational Biology research group, University of Vienna, A-1090 W盲hringerstra脽e 17, Vienna, Austria
  25. RTH, Univ. Copenhagen, Gr酶nneg氓rdsvej 3, Frederiksberg C, Denmark
  26. Santa Fe Institute, 1399 Hyde Park Rd., Santa Fe, USA
  
• ISSN：1611-3349

文摘

Circularized RNAs have received considerable attention is the last few years following the discovery that they are not only a rather common phenomenon in the transcriptomes of Eukarya and Archaea but also may have key regulatory functions. This calls for the adaptation of basic tools of sequence analysis to accommodate cyclic sequences. Here we discuss a common formal framework for linear and circular alignments as partitions that preserve (cyclic) order. We focus on the similarities and differences and describe a prototypical ILP formulation.