Efficient solutions for the far from most string problem

Annals of Operations Research. 2012. P. 663–682.

Festa P., Пардалос П. О.

Вычислительная молекулярная биология является одной из самых интересных междисциплинарных сфер исследований. В настоящее время она приносит пользу своими концепциями и теоретическими результатами, получаемыми различными научными исследовательскими сообществами, в том числе генетическими, биохимическими и сообществами в сфере информатики. В последние годы было показано, что многие молекулярные проблемы биологии могут быть сформулированы как задачи комбинаторной оптимизации, в том числе задачи последовательного совпадения, задачи перестройки генома, задача выбора и сравнения генетических цепочек, а также прогнозирование структуры белков и распознавание. Эта статья предоставляет детальное описание задач выбора и сравнения генетических цепочек. Для поиска качественных решений определенного класса задач молекулярной биологии, связанного с задачей сравнения генетических цепочек, мы предлагаем новые эвристические теории, включая процесс жадного рандомизированного адаптивного поиска(GRASP) и также генетический алгоритм(GA). Вычислительные результаты показывают, что эти рандомизированные эврестические теории дают более качественные результаты по сравнению с результатами, полученными с помощью лучших современных эвристических подходов.

Ключевые слова: комбинаторная оптимизация, combinatorial optimization, метаэвристика, Computational biology, Molecular structure prediction, Protein and sequences alignment, Metaheuristics, Вычислительная биология, Предвычисление молекулярной структуры, Белковое и последовательное совпадение, алгоритмы решения задач вычислительной и дискретной математики, методы получения биомедицинской информации, математические модели биологии