С точки зрения алгоритма построения оптимального выравнивания введение весовых матриц ничего не меняет. Однако оказывается, что нельзя рассматривать удаление одного символа как отдельное эволюционное событие. Вес нужно приписывать удалению целого фрагмента, и этот вес должен зависеть от длины фрагмента. Ограничения на выбор функции G(L) штрафов за удаление фрагментов (L - длина удаляемого фрагмента) влияют на эффективность построения оптимального выравнивания. В простейшем случае посимвольных замен (этот случай соответствует функции G(L)=k•L, где k - штраф за удаление одного символа) время работы квадратично зависит от длины сравниваемых слов (считаем, что их длины примерно равны), а в случае допустимости произвольных штрафных функций порядок роста времени работы соответствующего алгоритма - кубический. Компьютерные эксперименты показали, что разумным компромиссом служат линейные функции вида G(L)=k•L+s, где s - штраф за начало удаления/вставки, где k и L имеют тот же смысл, что и раньше. Для таких функций можно построить квадратичный по времени работы алгоритм построения оптимального выравнивания (хотя и с большей константой пропорциональности).