Алгебра спектральных преобразований в задачах обработки данных
Диссертация
Диссертационная работа посвящена изложению и обсуждению нового вычислительного метода, предложенного на основании проведенных нами исследований и позволяющего существенно понизить временную сложность спектральных вычислений для ряда основных аналитических преобразований функций и групп их суперпозиций. Вычислительный метод основан на знании полученных рекуррентных соотношений определенного вида… Читать ещё >
Список литературы
- Andreas de Vries «Algorithms and Data Structures», VorlesungWirt-schaftsinformatik, 2005.
- Andreas Solymosi and Ulrich Grude. Grundkurs Algorithmen und Datenstrukturen in Java. Vieweg, Braunschweig Wiesbaden, 2002.
- Arbter K., Snyder W. E., Burkhardt H., and Hirzinger G. Application of Affine-Invariant Fourier Descriptors to Recognition of 3-D Objects. IEEE Trans. Pattern Analy. Machine Intell., 12:640 647, 1990.
- Armin P. Barth. Algorithmik fur Einsteiger. Vieweg, Braunschweig Wiesbaden, 2003.
- Arun Krishnan, Francis Tang «Exhaustive whole-genome tandem repeats search» Bioinformatics vol. 20 issue 16 no. 16, pages 27 022 710, Oxford University Press, 2004.
- Becker, S. (1996). «Mutual information maximization: Models of cortical self-organization.» Network: Computation in Neural Systems 7(1): 7−31.
- Ben-Dor, A., Shamir, R. and Yakhini, Z. (1999). «Clustering gene expression patterns.» J Comput Biol 6(3−4): 281−97.
- Benson G. (1999) Tandem repeats finder: a program to analyze DNA sequences, Nucl. Acids Res., V. 27, issue 2, pp. 573−580.
- Benson, G. (1995) A space efficient algorithm for finding best scoring non-overlapping alignments. Theor. Comput. Sci., 145, 357−369.
- Benson, G. (1997) Sequence alignment with tandem duplication. J. Comput. Biol., 4, 351−367.
- Berriz, G.F., King, O.D., Bryant, В., Sander, C. and Roth, F.P. (2003). «Characterizing gene sets with FuncAssociate.» Bioinformatics 19(18): 2502−2504. Clustering Genes using Gene Expression and Text Literature Data
- Bickel, S. and Tobias, S. (2004). Multi-View Clustering. Proceedings of the Fourth IEEE International Conference on Data Mining (ICDM'04).
- Alferez Ronald and Wang Yuan-Fang, Geometric and Illumination Invariants for Object Recognition, Department of Computer Science, University of California, 1998.
- Bozdech, Z., Llinas, M., Pulliam, B.L., Wong, E.D., Zhu, J.C. and DeRisi, J.L. (2003). «The transcriptome of the intraerythrocytic developmental cycle of Plasmodium falciparum.» Plos Biology 1(1): 85−100.
- Britenkov A.K., Pankratov A.N. Stable Algorithms of Adaptive Approximation for Acoustic Signals Description by Orthogonal Polynomials// Physics of Wave Phenomena, 2004, Vol.12, № 3, pp.168−174
- Саппу John, «A Computational Approach to Edge Detection,» IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 8, no. 6, pp. 679−698, November 1986.
- Chaussabel, D. and Sher, A. (2002). «Mining microarray expression data by literature profiling.» Genome Biol 3(10): RESEARCH0055.
- Chiang, J.H. and Yu, H.C. (2003). «MeKE: discovering the functions of gene products from biomedical literature via sentence alignment.» Bioinformatics 19(11): 1417−1422.
- Collins, F.S. et al. (2003) The Human Genome Project: lessons from large-scale biology. Science, 300, 286−290.
- Collins, J.R., Stephens, R.M., Gold, В., Long, В., Dean, M. and Burt, S.K. (2003) An exhaustive DNA micro-satellite map of the human genome using high performance computing. Genomics, 82, 10−19.
- Djukova E.V., Inyakin A.S., and Peskov N.V. Methods of Combinatorial Analysis in Synthesis of Efficient Recognition Algorithms // Pattern Recognition and Image Analysis, 2003. V. 13. № 2. P. 426.
- Donald E. Knuth. The Art of Computer Programming. 1. Fundamental Algorithms. Addison-Wesley, Reading, 3rd edition, 1997.
- Donald E. Knuth. The Art of Computer Programming. 3rd Sorting and Searching. Addison-Wesley, Reading, 3rd edition, 1998.
- Eisen, M.B., Spellman, P.T., Brown, P.O. and Botstein, D. (1998). «Cluster analysis and display of genome-wide expression patterns.» Proceedings of the National Academy of Sciences of the United States of America 95(25): 14 863−14 868.
- EH Saber, and A. Murat Tekalp, «Region-Based Shape Matching for Automatic Image Annotation and Query-by-Example» Journal of visual communication and image representation, Vol. 8, No. 1, March, pp. 3−20,1997.
- Fleischmann, W., Moller, S., Gateau, A. and Apweiler, R. (1999). «A novel method for automatic functional annotation of proteins.» Bioinformatics 15(3): 228−233.
- Frazier, M.E. et al. (2003) Realizing the potential of the genome revolution: the genomes to life program. Science, 300, 290−293.
- Friedhelm Padberg. Elementare Zahlentheorie. Spektrum Akademischer Verlag, Heidelberg Berlin, 2nd edition, 1996.
- Fu, Y.H. et al. (1992) An unstable triplet repeat in a gene related to myotonic muscular dystrophy. Science, 255, 1256−1258.
- Getz, G., Levine, E. and Domany, E. (2000). «Coupled two-way clustering analysis of gene microarray data.» Proc Natl Acad Sci USA 97(22): 12 079−84.
- Gibbons, F.D. and Roth, F.P. (2002). «Judging the quality of gene expression-based clustering methods using gene annotation.» Genome Research 12(10): 1574−1581.
- Glenisson, P., Antal, P., Mathys, J., Moreau, Y. and De Moor, B. (2003). «Evaluation of the vector space representation in text-based gene clustering.» Рас Symp Biocomput: 391−402.
- Glenisson, P., Mathys, J. and De Moor, B. (2004). «Meta-Clustering of Gene Expression Data and Literature-based Information.» SIGKDD Explorations 5(2): 101−112.
- Gravano, L., Garcia-Molina, H. and Tomasic, A. (1999). «Gloss: Text-source discovery over the internet.» ACM Transactions on Database Systems 24(2): 229−264.
- Groult, R., Leonard, M. and Mouchard, L. (2002) Evolutive tandem repeats using Hamming distance. In Proceedings of 27th Symposium on Mathematical Foundations of Computer Science, Warsaw, Poland, August 2002, Springer, pp. 292−304.
- Groult, R., Leonard, M. and Mouchard, L. (2003) Speeding up the detection of evolutive tandem repeats. In Proceedings of The Prague Stringology Conference '03.
- Groult, R., Leonard, M. and Mouchard, L. (2004) Speeding up detection of evolutive tandem repeats. Theor. Сотр. Sci., 310, 309−328.
- ISO/IEC JTC1/SC29/WG11, Coding of Moving Pictures and Audio: MPEG-4 Video Verification Model version 18.0, JTC1/SC29/WG11 N3908, Pisa, January 2001.
- Jain, A.K. and Dubes, R.C. (1988). Algorithms for clustering data, Prentice Hall.
- Jenssen, Т.К., Laegreid, A., Komorowski, J. and Hovig, E. (2001). «A literature network of human genes for high-throughput analysis of gene expression.» Nat Genet 28(1): 21−8.
- Joint Video Team of ISO/IEC MPEG and ITU-T VCEG, Joint Final Committee Draft (JFCD) of Joint Video Specification (ITU-T Rec. H.264 | ISO/IEC 14 496−10 AVC), JVTD157, Australia, July 2002.
- Kannan, S.K. and Myers, E.W. (1996) An algorithm for locating regions of maximum alignment score. SIAM J. Comput., 25, 648−662.
- Kasturi J. and Acharya R. (2004). Clustering of diverse genomic data using information fusion Proceedings of the 2004 ACM symposium on Applied computing Nicosia, Cyprus ACM Press: 116−120
- Katti, M.V. et al. (2000) Amino acid repeat patterns in protein sequences: their diversity and structural-functional implications. Protein Sci., 9, 1203−1209.
- Kiranyaz S., Caglar K., Guldogan O., and Karaoglu E" «MUVIS: A Multimedia Browsing, Indexing and Retrieval Framework», Proc. of Third International Workshop on Content Based Multimedia Indexing, CBMI2003, Rennes, France, 22−24 September 2003.
- Kiranyaz S., Ferreira M. and Gabbouj M. «A novel feature extraction method based on segmentation over edge field for multimedia indexing and retrieval», Institute of Signal Processing, Tampere University of Technology, Tampere, Finland.
- Kitada, H. et al. (1996) Multiple alignment of biological sequences containing tandem repeats. Genome Inform., 7, 276−277.
- Kober V.I., M. G. Mozerov, J. Alvarez-Borrego and I. A. Ovseyevich. Nonlinear Image Processing with an Adaptive Structural Element // Pattern Recognition and Image Analysis, 2003. V. 13. No. 3. P. 476.
- Kolpakov, R et al. (2003) mreps: Efficient and flexible detection of tandem repeats in DNA. Nucleic Acids Res., 31, 3672−3678.
- Kolpakov, R. and Kucherov, G. (2003) Finding approximate repetitions under Hamming distance. Theor. Com. Sci., 303, 135−156.
- Korotkov E.V., Korotkova M.A. (1995) Latent periodicity of DNA sequences from some human gene regions, DNA Seq., V.5, pp.353 358.
- Korotkov E.V., Korotkova M.A., Kudryashov N.A. (2003) Information decomposition method to analyze symbolical sequences. Phys. Lett. A, 312: 198−210
- Kotel’nikov I.V. Algorithmic Models for Solving Pattern Recognition Problems 11 Pattern Recognition and Image Analysis, 1999. V. 9. № 1. P. 7.
- Kurtz, S., Choudhuri, J.V., Ohlebusch, E., Schleiermacher, C., Stoye, J. and Giegerich, R. (2001) REPuter: the manifold applications of repeat analysis on a genomic scale. Nuclei с Acids Res., 29,4633^1642.
- Landau, G.M. and Schmidt, J.P. (1993) An algorithm for approximate tandem repeats. In Proceedings of the. 4th Annual Symposium on Combinatorial Pattern Matching, Lecture Notes in Computer Science, Springer-Verlag, Vol. 648, pp. 120−133.
- Landau, G.M. and Vishkin, U. (1989) Fast parallel and serial approximate string matching. J. Algorithm., 10,157−169.
- Landau, G.M. et al. (1998) Incremental string comparison. SIAM J. Comput., 27, 557−582.
- Landau, G.M. et al. (2001) An algorithm for approximate tandem repeats. J. Comput. Biol., 8, 1−18.
- Landau, G.M., Schmidt, J.P. and Sokol, D. (2001) An algorithm for approximate tandem repeats. J. Сотр. Biol., 8, 1−18.
- Lempel A., Ziv J. (1976) On the Complexity of Finite Sequences. IEEE Transactions on Information Theory, V. IT-22, 75.
- Levenshtein, V.I. (1966) Binary codes capable of correcting, deletions, insertions and reversals. Soviet Phys. Dokl., 10, 707−710.
- Main, M.G. and Lorentz, R.J. (1984) An 0(n logn) algorithm for finding all repetitions in a string. J. Algorithm., 422432.
- Moore G.E. (1965) Cramming more components onto integrated circuits, Electronics Magazine, V. 38, no. 8, pp. 114−117.
- Noe L., Kucherov G. (2004) Improved hit criteria for DNA local alignment, BMC Bioinformatics, V. 5, 149 (http://www.biomedcentral.eom/1471−2105/5/149).
- Ralf Hartmut Guting. Datenstrukturen und Algorithmen. B.G. Teubner, Stuttgart, 1997.
- Raychaudhuri, S., Chang, J.T., Imam, F. and Altman, R.B. (2003). «The computational analysis of scientific literature to define and recognize gene expression clusters.» Nucleic Acids Research 31(15): 4553−4560.
- Raychaudhuri, S., Chang, J.T., Sutphin, P.D. and Altman, R.B. (2002). «Associating genes with gene ontology codes using a maximum entropy analysis of biomedical literature.» Genome Research 12(1): 203−214.
- Robert Sedgewick. Algorithmen in C. Addison-Wesley, Bonn, 1992. 89
- Roberts, R.J. (2001). «PubMed Central: The Gen-Bank of the published literature.» Proc Natl Acad Sci U S A 98(2): 381−2.
- Roth, F.P., Hughes, J.D., Estep, P.W. and Church, G.M. (1998). «Finding DNA regulatory motifs within unaligned noncoding sequences clustered by whole-genome mRNA quantitation.» Nature Biotechnology 16(10): 939−945.
- Sagot, M. and Myers, E.W. (1998) Identifying satellites in nucleic acid sequences. In Second Annual International Conference on Research in Computational Molecular Biology (RECOMB).ACM Press, New York, pp. 234−242.
- Schmidt, J.P. All highest scoring paths in weighted grid graphs and their application to finding all approximate repeats in strings. SI AM J. Comput., 27,972−992.
- Sergunin S.Yu., Kvashnin K.M., and M.I. Kumskov M.I. Image Representation in the Recognition Problem on the Basis of Symbol Marking of Its Singular Points // Pattern Recognition and Image Analysis, 2003. V. 13. № 1. P. 170.
- Sharma D, Issac B, Raghava GPS, Ramaswamy R (2004) Spectral Repeat Finder (SRF): identification of repetitive sequences using Fourier transformation. Bioinformatics, 20(9): 1405−1412
- Sokol Dina, Benson Gary and Tojeira Justin «Tandem repeats over the edit distance» Vol. 23 ECCB, pages e30-e35, Oxford University Press, 2006.
- Stephen C. Kleene. Turing’s Analysis of Computability, and Major Applications of It'. In Rolf Herken, editor, The Universal Turing Machine. A Half-Century Survey, Wien, 1994. SpringerVerlag.
- Stolovitzky, G., Gao, Y., Floratos, A. and Rigoutsos, I. (2001) Tandem repeat detection using pattern discovery, with applications to identification of yeast satellites. Technical Report RC 21 508. IBM T. J. Watson Research Center, Cambridge.
- Tamames, J., Ouzounis, C., Casari, G., Sander, C. and Valencia, A. (1998). «EUCLID: automatic classification of proteins in functional classes by their database annotations.» Bioinformatics 14(6): 542−543.
- Tanabe, L., Scherf, U., Smith, L.H., Lee, J.K., Hunter, L. and Weinstein, J.N. (1999). «Med-Miner: an Internet text-mining tool forbiomedical information, with application to gene expression profiling.» Biotechniques 27(6): 1210−4, 1216−7.
- Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest. Introduction to Algorithms.
- Thomas Ottmann and PeterWidmayer. Algorithmen und Datenstrukturen. Spektrum Akademischer Verlag, Heidelberg Berlin, 4rd edition, 2002.
- Turing Machine. A Half-Century Survey, pages 207−235. Springer-Verlag, Wien, 1994.
- Ukkonen, E. (1983) On approximate string matching. In Proceedings of the International Conference Foundations of Computation Theory, Lecture Notes in Computer Science 158, Springer-Verlag, pages 487−495.
- Volker Heun. Grundlegende Algorithmen. Vieweg, Braunschweig Wiesbaden, 2000.
- Watson J.D., Crick F.H.C. (1953) Molecular Structure of Deoxypentose Nucleic Acids. Nature, V. 171, p. 737.
- Wexler, Y., Yakhini, Z" Kashi, Y. and Geiger, D. (2004) Finding approximate tandem repeats in genomic sequences. In Proceedings of the 8th Annual Conference on Research in Computational Molecular Biology (RECOMB).
- William H. Press, Saul A. Teukolsky, William T. Vetterling, and Brian P. Flannery. Numerical Recipes in С++. The Art of Scientific Computing. Cambridge University Press, Cambridge, 2nd edition, 2002.
- Wirth N. Algorithmen und Datenstrukturen. B.G. Teubner, Stuttgart Leipzig, 1999.
- Yang Chengyong, Zeng Erliang, Li Tao, and Narasimhan Giri, Clustering Genes using Gene Expression and Text Literature Data,
- Bioinformatics Research Group (BioRG), School of Computer Science, Florida International University, Miami, Florida
- Александров A.A. и др. (1990) Компьютерный анализ генетических текстов, М.:Наука, 264 с.
- Бухберг Б., Калме Ж., Калтофен Э., Коллинз Дж., Лауэр М., Лафон Ж., Лоос Р., Минньотт М., Нойбюзер Й., Норманн А., Уинклер Ф., Я. Ван Хюльзен, «Компьютерная алгебра: Символьные и алгебраические вычисления» Пер. с англ. М.: Мир, 1986. — 392 с.
- Гасфилд Д. (2003) Строки, деревья и последовательности в алгоритмах. СПб.: Невский проспект, с. 225. (Dan Gusfield (1997) Algorithms on String, Trees, and Sequences University of California, Davis, P. 255).
- Горбань A.H., Миркес E.M., Попова Т. Г., Садовский М. Г. (1993) Новый подход к изучению статистических свойств генетических последовательностей. Биофизика, Т. 38, Вып. 5, с. 762−767.
- Горелик А.Л., Скрипкин В. А. Методы распознавания. М.: Высш. шк., 1977.
- Дедус Ф.Ф. Аналитическое представление экспериментальных данных и их обработка. Кибернетика и вычислительная техника. Вып.74, «Наукова думка», Киев, 1987.
- Дедус Ф.Ф., Гальченко А. А., Малахов В. Н. и др. Разработка методов и аппаратуры помехоустойчивого преобразования информации. Отчет по НИР. Номер гос. регистрации 76 047 147. Пущино: НИВЦ АН СССР, 1982.
- Дедус Ф.Ф., Куликова Л. И., Панкратов А. Н., Тетуев Р. К. «Классические ортогональные базисы в задачах аналитического описания и обработки информационных сигналов», М., Факультет ВМиК МГУ им. М. В. Ломоносова, 2004 г.
- Дедус Ф.Ф., Махортых С. А., Устинин М. Н., Дедус А. Ф., «Обобщенный спектрально-аналитический метод обработки информационных массивов», М., Машиностроение, 1999 г.
- Джунгурова О.С. «Реализация некоторых операций над отрезками ортогональных рядов полиномов Кравчука», Математические методы распознавания образов: 12 я Всероссийская конференция: Сборник докладов. М.: МАКС Пресс, 2005.-500 с.
- Дуда Р., Харт П. Распознавание образов и анализ сцен. М.: Мир, 1976.
- Загоруйко Н.Г. Методы распознавания и их применение. М.: Сов. радио, 1972.
- Гук М. Процессоры Pentium II, Pentium Pro и просто Pentium -СПб: Питер Ком, 1999. 288 с.
- Качмаж С., Штейнгауз С. «Теория ортогональных рядов», М.: Физматгиз, 1958 г.
- Колмогоров А.Н. (1987) Теория информации и теория алгоритмов. М.: Наука, 213 с.
- Кропотов А.И., «Николай Яковлевич Сонин», Л., Наука, 1967 г.
- Курант Р., Гильберт Д. Методы математической физики, т. 1, М.-Л., Гостехиздат, 1951.
- Математический энциклопедический словарь (гл. редактор Ю. В. Прохоров), М.: Советская энциклопедия, 1988 г.
- Махортых С.А., Панкратов А. Н. О спектральном разложении нерегулярных кривых. В кн. Доклады I Всероссийской конференции «Спектральные методы обработки информации в научных исследованиях» («Спектр — 2000»), М.: Алеф, 2000, 4446.
- Натансон И.П. «Теория функций вещественной переменной» изд. 2, М.: Гостехиздат, 1957 г.
- Никифоров А.Ф., Уваров В. Б., «Специальные функции математической физики», М., Наука, 1978 г.
- Никифоров А.Ф., Суслов С. К., Уваров В. Б. Классические ортогональные полиномы дискретной переменной. // М.: Наука. 1985.216 с.
- Новикова Д.А., Поволоцкий А. В. «Формулы для преобразования функций в пространстве коэффициентов разложения по базису полиномов Чебышева второго рода» М.: Сборник статей молодых ученных ВМиК МГУ, 2007, выпуск № 4, с. 1−8.
- Панкратов А.Н., «О реализации алгебраических операций над рядами ортогональных функций», Журнал вычислительной математики и математической физики, 2004, с. 2121−2127.
- Патрик Э. Основы теории распознавания образов. М.: Сов. радио, 1980.
- Семенюк В. В. «Современные методы и стандарты экономного кодирования видеоинформации», Санкт-Петербург, специально для http://www.compression.ru, 2002.
- Толстов Г. П. «Ряды Фурье», изд. 2, М.: Физматгиз, 1960 г. 390 с.
- Трикоми Ф. «Дифференциальные уравнения», Изд. 2-е, М.: Едиториал УРСС, 2003. 352 с.
- Фу К. С. Последовательные методы в распознавании образов и обучении машин-М.: Наука, 1971.
- Фу К. С. Структурные методы в распознавании образов. М.: Мир, 1977.
- Чебышев П.Л. «Вопросы о наименьших величинах, связанных с приближенным представленных функций», том 2., М.-Л., 1947 г., с. 151−235.