Алгоритм Руццо – Томпы

Алгоритм Руццо-Томпы или алгоритм RT. ^{[ 1 ]} представляет собой с линейным временем алгоритм для поиска всех непересекающихся, смежных подпоследовательностей с максимальным количеством очков в последовательности действительных чисел. ^{[ 2 ]} Алгоритм Руццо-Томпы был предложен Уолтером Л. Руццо и Мартином Томпа. ^{[ 3 ]} Этот алгоритм является усовершенствованием ранее известных алгоритмов квадратичного времени. ^{[ 1 ]} Подпоследовательность максимального результата из набора, созданного алгоритмом, также является решением проблемы максимального подмассива .

Алгоритм Руццо-Томпы имеет приложения в биоинформатике . ^{[ 4 ]} парсинг веб-страниц , ^{[ 5 ]} и поиск информации . ^{[ 6 ]}

Приложения

Биоинформатика

Алгоритм Руццо-Томпы использовался в инструментах биоинформатики для изучения биологических данных. Проблема нахождения непересекающихся максимальных подпоследовательностей имеет практическое значение при анализе ДНК . Алгоритмы максимальных подпоследовательностей использовались для идентификации трансмембранных сегментов и оценки гомологии последовательностей . ^{[ 4 ]}

Алгоритм используется для выравнивания последовательностей , которое используется как метод идентификации сходных ДНК , РНК или белков . последовательностей ^{[ 7 ]} Учет порядка пар подпоследовательностей с высокой оценкой в двух последовательностях обеспечивает лучшее выравнивание последовательностей. Это связано с тем, что биологическая модель предполагает, что отдельные пары подпоследовательностей с высокой оценкой возникают в результате вставок или делеций внутри совпадающей области. Требование последовательного упорядочения пар подпоследовательностей с высокой оценкой увеличивает их статистическую значимость. ^{[ 4 ]}

Парсинг веб-страниц

Алгоритм Руццо-Томпы используется при парсинге веб-страниц для извлечения информации с веб-страниц. Пастернак и Рот предложили метод извлечения важных блоков текста из документов HTML. Веб-страницы сначала токенизируются , и оценка каждого токена определяется с помощью локальных классификаторов уровня токена. ^{[ 8 ]} Затем используется модифицированная версия алгоритма Руццо-Томпы для поиска k подпоследовательностей токенов с самым высоким значением. Эти подпоследовательности затем используются в качестве прогнозов важных блоков текста в статье. ^{[ 5 ]}

Поиск информации

Алгоритм Руццо-Томпы использовался в алгоритмах поиска информации . Лян и др. предложил метод объединения данных для объединения результатов поиска нескольких алгоритмов поиска по микроблогам. используется алгоритм Руццо-Томпы . В их методе для обнаружения всплесков информации ^{[ 6 ]}

Определение проблемы

Задача нахождения всех максимальных подпоследовательностей определяется следующим образом: дан список действительных пронумерованных оценок. $x_{1},x_{2},\ldots ,x_{n}$ , найдите список смежных подпоследовательностей, дающих наибольший общий балл, где балл каждой подпоследовательности $S_{i,j}=\sum _{i\leq k\leq j}x_{k}$ . Подпоследовательности должны быть непересекающимися (непересекающимися) и иметь положительную оценку. ^{[ 9 ]}

Другие алгоритмы

Существует несколько подходов к решению проблемы всех максимальных подпоследовательностей. Естественный подход — использовать существующие алгоритмы с линейным временем для поиска максимальной подпоследовательности (см. задачу о максимальном подмассиве ), а затем рекурсивно найти максимальные подпоследовательности слева и справа от максимальной подпоследовательности. Анализ этого алгоритма аналогичен анализу быстрой сортировки : максимальная подпоследовательность может быть небольшой по сравнению с остальной частью последовательности, что приводит к времени выполнения $O(n^{2})$ в худшем случае.

Алгоритм

На этой анимации показан алгоритм Руццо-Томпы, работающий с входной последовательностью из 11 целых чисел, каждое из которых представлено отрезком линии на графике. Сегменты, выделенные жирными линиями, представляют собой максимальные найденные на данный момент сегменты. Анимация показывает состояние

I,R

и

L

на каждом шагу. Ниже показано текущее состояние алгоритма, которое соответствует шагам 1–4 в разделе «Алгоритм» на этой странице. Красное выделение показывает алгоритм, находящий значение для

j

на шагах 1 и 3. Если значение

j

удовлетворяет неравенствам на этих шагах, выделение становится зеленым. В конце анимации максимальные подпоследовательности будут выделены жирным шрифтом и отображены в

I

. ^{[ 1 ]}

Стандартная реализация алгоритма Руццо-Томпы работает в $O(n)$ время и использует O ( n пространство ), где n — длина списка оценок. Алгоритм использует динамическое программирование для постепенного построения окончательного решения путем постепенного решения все более крупных подмножеств проблемы. Описание алгоритма, предоставленное Руццо и Томпой, выглядит следующим образом:

Прочитайте баллы слева направо и подсчитайте совокупную сумму прочитанных баллов. Ведение упорядоченного списка

I_{1},I_{2},\ldots ,I_{j}

непересекающихся подпоследовательностей. Для каждой подпоследовательности

I_{j}

, запишите совокупный итог

L_{j}

всех баллов до, но не включая крайнего левого балла

I_{j}

, и общая сумма

R_{j}

до крайнего правого балла включительно

I_{j}

.

Списки изначально пусты. Результаты считываются слева направо и обрабатываются следующим образом. Неположительные оценки не требуют специальной обработки, поэтому считывается следующая оценка. Положительная оценка включается в новую подпоследовательность.

I_{k}

длины один, который затем интегрируется в список с помощью следующего процесса:

Список $I$ ищется справа налево для максимального значения $j$ удовлетворяющий $L_{j}<L_{k}$
Если такого нет $j$ , затем добавьте $I_{k}$ до конца списка.
Если есть такой $j$ , и $R_{j}\geq R_{k}$ , затем добавьте $I_{k}$ до конца списка.
В противном случае (т.е. существует такой aj, но $R_{j}<R_{k}$ ), расширить подпоследовательность $I_{k}$ влево, чтобы охватить все, вплоть до самого левого балла в $I_{j}$ . Удалить подпоследовательности $I_{j},I_{j}+1,\ldots ,I_{k}-1$ из списка и добавьте $I_{k}$ до конца списка. Пересмотрите недавно расширенную подпоследовательность $I_{k}$ (сейчас нумерация изменена $I_{j}$ ), как в шаге 1.

После достижения конца ввода все подпоследовательности, оставшиеся в списке

I

являются максимальными. ^{[ 2 ]}

Следующий код Python реализует алгоритм Руццо-Томпы:

def ruzzo_tompa(scores):
	"""Ruzzo–Tompa algorithm."""
	k = 0
	total = 0
	# Allocating arrays of size n
	I, L, R, Lidx = [[0] * len(scores) for _ in range(4)]
	for i, s in enumerate(scores):
    	total += s
    	if s > 0:
        	# store I[k] by (start,end) indices of scores
        	I[k] = (i, i + 1)
        	Lidx[k] = i
        	L[k] = total - s
        	R[k] = total
        	while True:
            	maxj = None
            	for j in range(k - 1, -1, -1):
                	if L[j] < L[k]:
                    	maxj = j
                    	break
            	if maxj is not None and R[maxj] < R[k]:
                	I[maxj] = (Lidx[maxj], i + 1)
                	R[maxj] = total
                	k = maxj
            	else:
                	k += 1
                	break
	# Getting maximal subsequences using stored indices
	return [scores[I[l][0] : I[l][1]] for l in range(k)]

См. также

Ссылки

^ Перейти обратно: ^а ^б ^с Спудж, Джон Л.; Рамирес, Леонардо Мариньо; Шитлин, Сергей Л. (2014). «Поиск повторов, как пример использования обобщенного алгоритма Руццо-Томпы для поиска оптимальных подпоследовательностей с пропусками» . Международный журнал исследований и приложений в области биоинформатики . 10 (4/5): 384–408. дои : 10.1504/IJBRA.2014.062991 . ISSN 1744-5485 . ПМК 4135518 . ПМИД 24989859 .
^ Перейти обратно: ^а ^б Руццо, Уолтер Л.; Мартин, Томпа (1999). «Алгоритм линейного времени для поиска всех подпоследовательностей с максимальным результатом» . Слушания. Международная конференция по интеллектуальным системам молекулярной биологии : 234–241. ISBN 9781577350835 . ПМИД 10786306 .
^ «Алгоритм линейного времени для поиска всех подпоследовательностей с максимальным результатом» (PDF) .
^ Перейти обратно: ^а ^б ^с Карлин, С; Альтшул, Сан-Франциско (15 июня 1993 г.). «Приложения и статистика для нескольких сегментов с высокими показателями в молекулярных последовательностях» . Труды Национальной академии наук Соединенных Штатов Америки . 90 (12): 5873–5877. Бибкод : 1993PNAS...90.5873K . дои : 10.1073/pnas.90.12.5873 . ПМК 46825 . ПМИД 8390686 .
^ Перейти обратно: ^а ^б Пастернак, Джефф; Рот, Дэн (2009). «Извлечение текста статьи из Интернета с максимальной сегментацией подпоследовательностей». Материалы 18-й международной конференции по Всемирной паутине . стр. 971–980. дои : 10.1145/1526709.1526840 . ISBN 9781605584874 . S2CID 346124 .
^ Перейти обратно: ^а ^б Лян, Шансонг; Рен, Чжаочунь; Веркамп, Воутер; Мейдж, Эдгар; де Рийке, Мартен (2014). «Агрегация рангов с учетом времени для поиска по микроблогам». Материалы 23-й Международной конференции ACM по управлению информацией и знаниями . стр. 989–998. CiteSeerX 10.1.1.681.6828 . дои : 10.1145/2661829.2661905 . ISBN 9781450325981 . S2CID 14287901 .
^ Спудж, Джон Л.; Мариньо-Рамирес, Леонардо; Шитлин, Сергей Л. (2012). «Алгоритм Руццо-Томпы может найти максимальные пути во взвешенных ориентированных графах на одномерной решетке» . 2012 г. Вторая международная конференция IEEE по вычислительным достижениям в био и медицинских науках (ICCABS) . стр. 1–6. дои : 10.1109/ICCABS.2012.6182645 . ISBN 978-1-4673-1321-6 . S2CID 14584619 .
^ «Парсинг веб-страниц: все, что вам нужно знать» . Датамам . 30 июля 2021 г. Проверено 16 февраля 2023 г.
^ Спудж, Джон Л.; Мариньо-Рамирес, Леонардо; Шитлин, Сергей Л. (2012). «Алгоритм Руццо-Томпы может найти максимальные пути во взвешенных ориентированных графах на одномерной решетке» . 2012 г. Вторая международная конференция IEEE по вычислительным достижениям в био и медицинских науках (ICCABS) . стр. 1–6. дои : 10.1109/ICCABS.2012.6182645 . ISBN 978-1-4673-1321-6 . S2CID 14584619 .

Дальнейшее чтение

Али, Сайед Арслан; Раза, Басит; Малик, Ахмад Камран; Шахид, Ахмад Раза; Фахим, Мухаммед; Алькухайз, Хани; Кумар, Йоган Джая (2020). «Оптимально настроенный и улучшенный подход Deep Belief Network (OCI-DBN) для прогнозирования заболеваний сердца на основе Руццо-Томпы и составного генетического алгоритма» . Доступ IEEE . 8 . Институт инженеров по электротехнике и электронике (IEEE): 65947–65958. дои : 10.1109/access.2020.2985646 . ISSN 2169-3536 . S2CID 215817246 .

[:0-1] Перейти обратно: ^а ^б ^с Спудж, Джон Л.; Рамирес, Леонардо Мариньо; Шитлин, Сергей Л. (2014). «Поиск повторов, как пример использования обобщенного алгоритма Руццо-Томпы для поиска оптимальных подпоследовательностей с пропусками» . Международный журнал исследований и приложений в области биоинформатики . 10 (4/5): 384–408. дои : 10.1504/IJBRA.2014.062991 . ISSN 1744-5485 . ПМК 4135518 . ПМИД 24989859 .

[ruzzo_tompa-2] Перейти обратно: ^а ^б Руццо, Уолтер Л.; Мартин, Томпа (1999). «Алгоритм линейного времени для поиска всех подпоследовательностей с максимальным результатом» . Слушания. Международная конференция по интеллектуальным системам молекулярной биологии : 234–241. ISBN 9781577350835 . ПМИД 10786306 .

[3] «Алгоритм линейного времени для поиска всех подпоследовательностей с максимальным результатом» (PDF) .

[karlin-4] Перейти обратно: ^а ^б ^с Карлин, С; Альтшул, Сан-Франциско (15 июня 1993 г.). «Приложения и статистика для нескольких сегментов с высокими показателями в молекулярных последовательностях» . Труды Национальной академии наук Соединенных Штатов Америки . 90 (12): 5873–5877. Бибкод : 1993PNAS...90.5873K . дои : 10.1073/pnas.90.12.5873 . ПМК 46825 . ПМИД 8390686 .

[pasternack-5] Перейти обратно: ^а ^б Пастернак, Джефф; Рот, Дэн (2009). «Извлечение текста статьи из Интернета с максимальной сегментацией подпоследовательностей». Материалы 18-й международной конференции по Всемирной паутине . стр. 971–980. дои : 10.1145/1526709.1526840 . ISBN 9781605584874 . S2CID 346124 .

[liang-6] Перейти обратно: ^а ^б Лян, Шансонг; Рен, Чжаочунь; Веркамп, Воутер; Мейдж, Эдгар; де Рийке, Мартен (2014). «Агрегация рангов с учетом времени для поиска по микроблогам». Материалы 23-й Международной конференции ACM по управлению информацией и знаниями . стр. 989–998. CiteSeerX 10.1.1.681.6828 . дои : 10.1145/2661829.2661905 . ISBN 9781450325981 . S2CID 14287901 .

[7] Спудж, Джон Л.; Мариньо-Рамирес, Леонардо; Шитлин, Сергей Л. (2012). «Алгоритм Руццо-Томпы может найти максимальные пути во взвешенных ориентированных графах на одномерной решетке» . 2012 г. Вторая международная конференция IEEE по вычислительным достижениям в био и медицинских науках (ICCABS) . стр. 1–6. дои : 10.1109/ICCABS.2012.6182645 . ISBN 978-1-4673-1321-6 . S2CID 14584619 .

[8] «Парсинг веб-страниц: все, что вам нужно знать» . Датамам . 30 июля 2021 г. Проверено 16 февраля 2023 г.

[9] Спудж, Джон Л.; Мариньо-Рамирес, Леонардо; Шитлин, Сергей Л. (2012). «Алгоритм Руццо-Томпы может найти максимальные пути во взвешенных ориентированных графах на одномерной решетке» . 2012 г. Вторая международная конференция IEEE по вычислительным достижениям в био и медицинских науках (ICCABS) . стр. 1–6. дои : 10.1109/ICCABS.2012.6182645 . ISBN 978-1-4673-1321-6 . S2CID 14584619 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]