Сериальное и комплексное описание строя компонентов в массивах данных | Вестн. Том. гос. ун-та. Управление, вычислительная техника и информатика. 2018. № 42. DOI: 10.17223/19988605/42/4

Сериальное и комплексное описание строя компонентов в массивах данных

Отмечено «интервальное» представление строя информационной цепи, числовые характеристики которого показали высокую чувствительность к расположению компонентов в «текстовых» массивах данных. Предложено «сериальное» представление строя цепи, числовые характеристики которого оценивают массивы, состоящие из чередующихся серий одинаковых данных. Вводится комплексное представление массивов, сформированных как отдельно стоящими разными элементами, так и чередующимися сериями одинаковых данных.

Serial and complex description of the order of components in data sets.pdf В работах [1, 2] введено понятие «строй цепи». Представим его компактное описание. Рассмотрим кортежи, представляющие собой комбинации типа «перестановки с повторениями», компонентами которых являются натуральные числа, не превышающие n (длина кортежа). В теоретико-множественном представлении такой кортеж называется вектором. Рассмотрим в множестве таких векторов подмножество векторов, первый компонент которых «единица», каждый следующий компонент с номером i < n либо представлен натуральным числом, равным компоненту-числу с номером j < i, либо этот компонент на единицу больше, чем максимальное компонент-число с номером k < i (где k Ф j). Назовем элемент этого подмножества «вектор строя» (далее - строй). Другими словами, строй цепи определен как особого рода кортеж, компонентами которого являются натуральные числа , где a\ = 1, an < n; если ak £ {01, 02, ..., ak-i], то ak = max{a1, 02, ..., ak-i} + 1. Заменим в любом кортеже длины n первые встречные разные компоненты (элементы алфавита мощностью m < n) возрастающими на единицу натуральными числами (начиная с единицы). Другие повторяющиеся одинаковые компоненты отметим теми же числами. Очевидно, что в результате любой кортеж преобразуется в вектор строя. В работах, представляющих средства формального описания и анализа строя цепи сообщений (ФОАС), рассматривались такие длинные кортежи (знаковые последовательности, большие массивы данных), в которых отдельные различные компоненты на протяжении цепи почти всегда чередуются, а серии (одинаковых подряд расположенных) сообщений редкие и короткие. Исследования таких разных по природе цепей, как литературные тексты, нотные записи музыкальных произведений, нуклео-тидные цепи (геномов прокариот), показали высокую чувствительность «интервальных» числовых характеристик строя (представленных целым комплексом) к расположению сообщений в цепи. Эффективность средств ФОАС при исследовании больших массивов данных, кроме прочего, обусловлена линейной зависимостью вычислительной сложности от длины последовательностей. Функции числовых характеристик строя эффективно представляют локальное расположение сообщений на разных участках цепи [2]. Заметим, что числовое отображение знаковой цепи позволяет применять разнообразные средства анализа сигналов (математический, спектральный, статистический и корреляционный анализ и др.). Наше особое внимание к исследованию символьных последовательностей объясняется недостатком адекватных средств для их описания и анализа. Предложенные ранее средства предполагают отображение знаковой цепи ее строем, в результате декомпозиции которого выделяются j-е неполные однородные цепи, в каждой из которых отмечены (натуральным числом) занятые места расположения одинаковых сообщений в количестве п- (остальные места на позиции всей цепи пустые). В качестве первичной измеримой единицы используется очередной (i-й) интервал между ближайшими занятыми местами, размер которого Ду определяется числом пустых мест плюс один. Таким образом, определяется расстояние от одного сообщения до ближайшего такого же (по-английски distance). Заметим, что учет интервалов между однородными заявками (событиями) издавна используется в теории массового обслуживания при моделировании потоков однородных и неоднородных случайных событий [3]. В последние годы [4, 5] учет интервалов находит распространение, в частности, при анализе нуклеотидных цепей (inter-nucleotide distance). Однако использование массивов интервалов знаковых последовательностей осуществляется традиционными математическими средствами, которые не позволяют осуществлять непосредственное описание и анализ расположения компонентов в целостной цепи. Очевидна необходимость разработки средств описания и анализа строя таких массивов данных, которые преимущественно представлены чередующимися сериями одинаковых сообщений. Это могут быть, например, оцифрованные изображения, последовательности измеряемых величин и т.п. В работе [2] представлены более подходящие для таких данных числовые характеристики строя. При этом используется декомпозиция знаковой цепи на неполные неоднородные цепи. Вначале счи-тывается неоднородная цепь, содержащая только первые встречные разные знаки. Такая цепь содержит весь алфавит или словарь (мощностью m) рассматриваемого массива. Затем - другая цепь, содержащая вторые встречные разные знаки, и т.д. 1. Сериальное описание строя цепи Для непосредственного учета чередующихся серий в массиве данных введем необходимые далее понятия и их обозначения. Назовем отрезком или серией упорядоченное множество одинаковых данных, выделенных подряд в составе j-й неполной однородной цепи. Допустим, что на позиции некоторого отрезка можно «считать» несколько серий по числу элементов в этом отрезке. В качестве первичной измеримой единицы используем длину серии, размер которой определяется числом занятых подряд мест в j-й однородной цепи. Наименьшая длина отрезка - единица. Для краткости будем употреблять термин «длина», величину которой обозначим т- (i - номер элемента в j-й однородной цепи). Назовем протяженностью данной серии логарифм ее длины Ц = log2 т-. Очевидно, протяженность отдельно стоящего элемента равна нулю. Сериальный объем j-й однородной цепи, составленной отрезками, определим в виде: ^j =П j Tj , (1) где i - номер элемента в j-й однородной цепи, а nj - число серий в j-й однородной цепи (при чтении серий начиная с каждого отмеченного в ней сообщения). Средняя геометрическая длина серий в j-й однородной цепи определяется в виде: тg = . (2) При этом сериальный объем j-й однородной цепи можно определить как V. = Tnj . (3) у g v ' Подставляя (1) в (2) определим % в виде: n X '=i Пу'. Логарифмируя (1), получим суммарную протяженность (далее - протяжение) всех серий j-й однородной цепи: m L = £log2 Xj . j=i Определим из (3) протяжение серий в j-й однородной цепи на основе их средней геометрической длины: Lj = • log' X^ . (4) Из (4) средняя протяженность серии в данной однородной цепи определится как lj = log2 T j . Суммарная и средняя длины всех серий j-й однородной цепи определяются, соответственно, в виде: nj s / si =Xxj , %ai = Yn, . j=1 7 1 Отношение средних длин (геометрического и арифметического) определим в виде: 5т. = T . j /т • / aj Эта величина является средней относительной (нормированной) длиной серий в j-й однородной цепи. В некотором смысле она аналогична длительности ноты в музыке, измеряемой в долях такта. Очевидно, 5ij максимально и равно единице, когда все отрезки в однородной цепи равны. Вероятно, эту величину можно назвать длительностью серий, или равносерийностью, или просто серийностью j-й однородной цепи. Сериальный объем полной неоднородной цепи определим произведением всех m j-х сериальных объемов: г,=п:л (5) Lj=1 Ч Суммарная и средняя длины всех серий m разных однородных цепей данного массива, соответственно, определяются как m s = У Sf, т„ = у , i-i j a /n j=1 где n - длина всей цепи данных. Определим среднюю геометрическую длину всех серий данного массива в виде: Tg = №. (6) Подставляя (1) в (5) и (5) в (6), определим эту величину как I m nj т=n П П т. у j=1 i=1 При этом сериальный объем массива данных можно определить из (6) в виде: Vt= Tg. (7) Отношение средних длин (геометрического и арифметического) назовем средней относительной (нормированной) длиной серий в строе цепи определим в виде: 5т = Tg/ . /Ta Эту величину можно назвать длительностью серий, или равносерийностью, или серийностью строя цепи. Логарифмируя (7) получим суммарную протяженность (протяжение) всех серий в полной неоднородной цепи: L = n • log' тg . Средняя протяженность серий в полной неоднородной цепи определится в виде: l = l0g2 Tg . Назовем «полным» сериальным описанием строя цепи, образованного только сериями данных, распределения суммарных и средних протяженностей j-х однородных цепей вида: {Lj}, {}, где j = 1, m. При компактном описании сериальных данных применимы разного рода числовые характеристики протяженности серий, а именно средняя протяженность, дисперсия, или СКО, протяженно-стей и центрированные моменты более высоких порядков. Наконец, отметим, что строй цепи, содержащий кроме «разряженных» данных также и их серии, следует описывать комплексами числовых характеристик и их распределений, учитывающих как интервалы и удаленности, так и длины серий и их протяженности. 2. Интервально-сериальное описание строя цепи Рассмотрим массив, содержащий как отдельно стоящие чередующиеся разные сообщения, так и серии идущих подряд одинаковых данных. Для описания строя такой информационной цепи также необходима предварительная ее декомпозиция на однородные цепи. Неполная j-я однородная цепь, на позиции которой некоторые места заняты (одинаковыми сообщениями), а другие пусты, может быть отображена как «интервальными», так и «сериальными» данными. При интервальном рассмотрении определяется упорядоченное множество интервалов вида: (Ди,Д2,V--,\j) . (8) При сериальном отображении получается кортеж длин серий вида: (т1у ,T2j ,...,Tj ,...,Tj). (9) Последовательности интервалов и длин j-й однородной цепи (8) и (9) комплементарно дополняют друг друга следующим образом: если А- > 2, то т- = 1; если т- > 2, то А- = 1. При сериальном отображении всех m j-х неполных однородных цепей и целого массива данных получаем набор сериальных характеристик строя т-, Vy-, Vt, t-, Tg, Ц = log Ttj, l. = log т., Lj = nj ■ log2 Tgj, l = log2 Tg, L = n ■ log2 тg . При интервальном отображении j-х неполных однородных цепей и полной неоднородной последовательности ранее получен аналогичный набор интервальных характеристик строя со следующими (уточненными здесь) обозначениями и наименованиями: Ду - интервал от i-го до (i + 1)-го ближайшего такого же сообщения в j-й однородной цепи; Vaj- - интервальный объем j-й однородной цепи; Va - интервальный объем полной неоднородной цепи; Д- - средний геометрический интервал в j-й однородной цепи; Ag - средний геометрический интервал в полной неоднородной цепи; gj = log2 Ду - удаленность (i + 1)-го сообщения относительно i-го в j-й однородной цепи; gj = log2 Д у - средняя удаленность сообщений в j-й однородной цепи; g = log2 Дg - средняя удаленность сообщений в полной неоднородной цепи; Gj = nj ■ log2 Д у - суммарная удаленность, или удаление, сообщений в j-й однородной цепи (ранее - глубина j-й цепи); G = n ■ log2 Дg - суммарная удаленность, или удаление, полной неоднородной цепи (ранее - глубина цепи). Отдельно запишем выражение, аналогичное (3), в котором интервальный объем j-й однородной цепи определен через средний геометрический интервал как Vv=Д». Произведение интервального и сериального объемов j-й однородной цепи назовем (полным) объемом j-й однородной цепи и запишем в виде: vj = Уду ■Vj . (10) Используя комплементарную дополнительность интервального (8) и сериального (9) представлений всех nj сообщений j-й однородной цепи, произведения пар интервалов и длин серий для каждого /-го сообщения запишем в виде: Uj Uj Uj П К)=П A,П т, = Vj V • (u) i=1 i=1 i=1 Из сравнения (10) и (11) видно, что одна и та же комплексная характеристика Vj может быть вычислена либо с раздельным определением интервальной и сериальной характеристик, либо - без раздельной оценки этих свойств j-й однородной цепи. Назовем емкостью i-го сообщения в j-й цепи произведение вида и = A • т • j j V «Емкостное» представление j-й однородной цепи, определенное кортежем вида v1j , v2 V vj VUjV не содержит компонентов, равных единице, так как V/j > 2 для любых компонентов, однако при этом интервальные и сериальные свойства цепи неразличимы. Для получения емкостных характеристик строя цепи применимы выражения, представленные выше. Введем обозначения и названия для некоторых из них v/j - емкость i-го сообщения в j-й однородной цепи; Vj - (емкостной) объем j-й однородной цепи; V - (емкостной) объем массива данных; Vgj - средняя геометрическая емкость сообщений в j-й однородной цепи; Vg - средняя геометрическая емкость сообщений в массиве данных; Су = log и - размер i-го сообщения в j-й однородной цепи; Cj = log и ■ - средний размер сообщений j-й однородной цепи; с = log и - средний размер сообщений в массиве данных; C ■ = и ■ • log v ■ - (полный) размер j-й однородной цепи; C = n • log2 vg - (полный) размер массива данных. Используя представленные характеристики, легко получить следующие выражения для комплексных характеристик строя цепи: V = Va • V, Ug = Ag-Tg, C = G + L, с = g +1, (12) Формула (12) в более подробном представлении имеет вид: m m с=m.log2Ag,, (13) v=1 V=1 Для псевдотекстовых регулярных массивов данных, у которых Ag = Аа;- = n /nj, первое слагаемое в (13) для n ^ да совпадает с энтропией; при любых других расположениях символов средняя удаленность сообщений в цепи, представленная первыми слагаемыми в (12) и (13), меньше числа идентифицирующих информаций (по М. Мазуру, [6]), т.е. g < И, а средний геометрический интервал меньше числа описательных информаций (по М. Мазуру), т.е. Ag < D. Важно заметить, что так же, как и у интервальных характеристик, время вычисления сериальных и емкостных характеристик линейно зависит от размера входных данных (длины последовательности). И, как следствие, они эффективны для обработки длинных последовательностей (больших массивов данных). Заключение Очевидно, что интервальные, сериальные и емкостные характеристики строя цепи попарно дополняют друг друга. Однако емкостные характеристики дают «полное» количественное описание массива данных, которое нельзя получить только интервальными или сериальными характеристиками. Полное описание строя интервальными характеристиками возможно только для «текстовых» массивов данных, где Ту = 1. Сериальные характеристики дают полное описание таких массивов, которые практически не имеют «точечных» данных, но состоят из длинных повторов (серий) одинаковых данных, где Д j = i. Дальнейшая разработка средств описания и анализа строя предполагает исследование свойств введенных здесь характеристик, а также возможную их модификацию. Так как представленные сериальные оценки предусматривают неоднократное чтение серий на позиции некоторого отрезка, в дальнейшем предусматривается разработка средств для однократного чтения отрезков с последующими исследованиями и сравнением чувствительности сериальных и «отрезочных» характеристик строя цепи. Компьютерная обработка больших «текстовых» массивов данных (проза, стихотворения, нотные записи, нуклеотидные последовательности) показала высокую чувствительность интервальных характеристик строя к оригинальному расположению компонентов (букв, слов, нот и т.п.) в длинных и очень длинных кортежах. Предполагается, что сериальные и емкостные характеристики строя обеспечат такие же свойства для массивов данных, содержащих длинные последовательности повторяющихся компонентов. Наконец, отметим, что разрабатываемые средства формального описания и анализа и большой набор его числовых характеристик отражают разнообразные свойства нового абстрактного объекта - строя информационной цепи.

Ключевые слова

строй цепи, числовые характеристики строя, удаленность сообщения, протяженность серии, межнуклеотидное расстояние, order, order characteristics, remoteness, spread of series, inter-nucleotide distance

Авторы

ФИООрганизацияДополнительноE-mail
Гуменюк Александр СтепановичОмский государственный технический университетдоцент, кандидат технических наук, доцент кафедры информатики и вычислительной техники факультета информационных технологий и компьютерных системgumas45@mail.ru
Всего: 1

Ссылки

Gumenyuk A., Kostyshin A., Simonova S. An approach to the research of the structure of linguistic and musical texts // Glottometrics. 2002. No. 3. P. 61-69.
Гуменюк А.С., Поздниченко Н.Н., Шпынов С.Н., Родионов И.Н. О средствах формального анализа строя нуклеотидных цепей // Математическая биология и биоинформатика. 2013. Т. 8, № 1. С. 373-397. URL: http://www.matbio.org/article.php?journ_id= 15&id=158 (дата обращения: 15.04.2016).
Вентцель Е.С. Исследование операций: задачи, принципы, методология. М. : Наука, 1988. 208 с.
Nair A.S., Mahalakshmi T. Visualization of genomic data using inter-nucleotide distance signals // Proc. of IEEE Genomic Signal Processing. Bucharest, 2005. URL:http://www.ece.iit.edu/~biitcomm/research/references/Achuthsankar%20S%20Nair/Visualization %20of%20genomic%20data%20using%20inter-nucleotide%20distance%20signals.pdf (access date: 21.12.17).
Afreixo V., Bastos C.A.C., Pinho A.J., Garcia S.P., Ferreira P.J.S.G. Genome analysis with inter-nucleotide distances // Bioinformatics. 2009. V. 25 (23). P. 3064-3070.
Мазур М. Качественная теория информации. М. : Мир, 1974. 240 с.
 Сериальное и комплексное описание строя компонентов в массивах данных | Вестн. Том. гос. ун-та. Управление, вычислительная техника и информатика. 2018. № 42. DOI: 10.17223/19988605/42/4

Сериальное и комплексное описание строя компонентов в массивах данных | Вестн. Том. гос. ун-та. Управление, вычислительная техника и информатика. 2018. № 42. DOI: 10.17223/19988605/42/4