Моделирование задачи оптимального выравнивания последовательностей
Автор: Знаменский Сергей Витальевич
Журнал: Программные системы: теория и приложения @programmnye-sistemy
Рубрика: Математические основы программирования
Статья в выпуске: 4 (22) т.5, 2014 года.
Бесплатный доступ
Выравнивание последовательностей широко используется в различных компьютерных системах для анализа и оценки близости данных, выделения изменений и родственных задач. Интуитивные требования к постановке задачи оптимального выравнивания последовательностей формализованы в приводимых тестах. Тесты показали, что ни один из широко используемых подходов к близости и выравниванию не соответствует этим требованиям. Описана новая модель минимизации конфликтов при слиянии изменений. Модель приводит к простой постановке задачи оптимального выравнивания последовательностей, удовлетворяющей рассмотренным требованиям.
Метрика левенштейна, непрерывная интеграция., расстояние редактирования, выравнивание последовательностей, сходство строк, разработка по
Короткий адрес: https://sciup.org/14335996
IDR: 14335996
Modeling of the optimal sequence alignment problem
The sequence alignmet is widely used in variouse computer systems for data similarity measure and analisys, changes detection and relative tasks. Some intuitive requirements for string alignmet are formalised in a test suite. The tests shows that none of existing approaches to string similarities and alingment meet the requirements. A new model of minimizing conflicts when merging changes is described. The model leads to a simple formulation of new optimization problem which meet the requirements. (In Russian.)
Список литературы Моделирование задачи оптимального выравнивания последовательностей
- Baudiˇ P., Current concepts in version control systems, 2014, arXiv: s 1405.3496.
- Hunt J. W., McIlroy M. D., An algorithm for differential file comparison, Bell Laboratories, 1976, 7 pp.
- Mackall M., “Towards a Better SCM: Revlog and Mercurial”, Proceedings of Linux Symposium. v. 2 (July 19-22, 2006, Ottawa, Ontario, Canada), 2006, pp. 83-90, URL http://mercurial.selenic.com/wiki/Presentations?action=AttachFile amp;do=get amp;target=ols-mercurial-paper.pdf.
- Левенштейн В. И., «Двоичные коды с исправлением выпадений и вставок символа 1», Пробл. передачи информ., 1:1 (1965), c. 12-25.
- MacDonald J., Versioned file archiving, compression and distribution, U.C. Berkeley, 1998, URL http://citeseerx.ist.psu.edu/viewdoc/summary?doi= 10.1.1.38.9429.
- Wieling M., Bloem J., Mignella K., Timmermeister M., Nerbonne J., “Measuring foreign accent strength in English. Validating Levenshtein Distance as a Measure”, The Mind Research Repository (beta), 2013, no. 1, URL http://openscience.uni-leipzig.de/index.php/mr2/article/view/41/30.
- Wu X., Wu Zh., Jia J., Meng H., Cai L., Li W., “Automatic speech data clustering with human perception based weighted distance”, The 9th International Symposium on Chinese Spoken Language Processing, ISCSLP 2014 (12-14 September 2014, Singapore), IEEE, pp. 216-220.
- Luo L., Ming J., Wu D., Liu P., Zhu S., “Semantics-based obfuscation-resilient binary code similarity comparison with applications to software plagiarism detection”, Proceedings of the 22nd ACM SIGSOFT International Symposium on Foundations of Software Engineering, FSE 2014 (November 16-21, 2014, Hong Kong, China), ACM, 2014, pp. 389-400, URL http://faculty.ist.psu.edu/wu/papers/cop-fse2014.pdf.
- Rho S., Hwang E., “FMF: Query adaptive melody retrieval system”, Journal of Systems and Software, 79:1 (2006), pp. 43-56.
- Durbin R., Eddy S., Krogh A., Mitchison G., Biological sequence analysis: probabilistic models of proteins and nucleic acids, Cambridge University Press, 1998, 356 pp.
- Dohrn H., Riehle D., “Fine-grained change detection in structured text documents”, Proceedings of the 2014 ACM symposium on Document engineering, DocEng 2014 (September 16-19, 2014, Denver, Colorado, USA), ACM, 2014, pp. 87-96.
- Oita M., Senellart P., “Deriving dynamics of web pages: A survey”, TWAW 2011: Temporal Workshop on Web Archiving (March 28, 2011, Hyderabad, India), 2011, URL http://pierre.senellart.com/publications/oita2011deriving.pdf.
- Hall P. A. V., Dowling G. R., “Approximate string matching”, ACM computing surveys, 12:4 (1980), pp. 381-402.
- Diamantopoulos T., Symeonidis A., “Localizing Software Bugs using the Edit Distance of Call Traces”, International Journal on Advances in Software, 7:1-2 (2014), pp. 277-288.
