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

российская академия наук

СИБИРСКОЕ ОТДЕЛЕНИЕ Новосибирски.! Институт органической химгя

i Га правах рукописи

Константинова Елена Валентинова

ГРА5Ы, ГШЕРГРАФЫ И ИХ ИНВАРИАНТЫ ДЛЯ ХАРАКТЕБНЗЛЦКМ МОЛЕЮГЖПШХ СТРУКТУР

05.1 Э. 1 fi-n. лдаившю :этчвсдителш& ïoxrsicrî, патзматшескогэ модояроздшя " .чатематаческ*лх котодоз в научшк псслздоваглтях (то.-.личбские иаукл)

Азюрофарат

диссертации на соискание учено:! степени кандидата технических наук

Ó' '

новосибирск - 1992

Робота выполнена в Институте Математики СО РАЯ. Научные руководители - доктор химических наук , ' ■ профессор Ю.С.Некрасов

- кандидат технических наук, .. с.н.с. В.А.Скоробогатов

Официальные оппоненты: - доктор физико-математических, наук .

профессор М.И. Нечеяурэнко,

- кандидат хшических наук -с.н.с. К.С. Лебедев. ■■ . '

Ведущзе предприятие: - Институт органический химии РАН

Защита диссертации состоится "14" апреля 1592 г.в 15 часов на заседании специализированного совета К 002.42.01 в Новосибирском института органической химии СО АН СССР по адресу: 630090, Новосибирск, пр. Aie. Лаврентьева, 9.

С диссертацией можно ознакомиться в библиотеке Новосибирского института органической химии СО АН СССР,

Автореферат разослан " _ "___¡__ 1992г.

Ученый секретарь специализированного соЕета^ кандидат физико-математических, каук ] Смирнов

от:.:!ЛЯ хлл^ТЕЛХ'Ж'Л ?л:,о"и

Тссруулчзскс? и т;р:п1ладво;: явллогея устлтюв--

:с-к;п сзрггсмх, сзсСсткоим п тк'яюпхшсй СПО-

: ::'г"-тьг1 у v,:, Лул л ли: у л i/' ппусг.о лслольгл/л, о л гул'о;":

.f.\'<V;.J:.Y' j.'Tc.,"; ■ .Г'7 Л "Л ЛЛЛ. Т.ЛОЛ.: Г г..;, ;; ' Г t. I- :TXV.r.i ГГЛЛ.ЛГ.

'е'ллл. л,, улсллчл: л ст:лллзшГ. ^ улл хлплкл пзиíc, л

■уЛсг .. -."у\-лл слулл: сснсллл пллтрсллл; :т>;влрлат;':г л, го.с--л;о лллллллую-лл лслл".:ллсгло:5 оОрг-.Оотко сурунулрллл "л-лллл'ль с тлл оллс:лу;.ллз ¡л.отодм гггллл1 авлтшл л

"лл.лгл лтруллур углгизсклл лл;дтеге::Л ocucesiiu .н:> ;гглл.:ене-ПЛТ Т.--ОГГ/"Л гралов И ПОЛЕОЛЛЮТ ОПКСМВЙТЬ ТОЛЛКО

•r.rrr;:y..x Г-vr.: jл; толег/л о козалитепви свявяка. r> сРллс-;л;лл1";л: rr.r,*ox ;:о учлтлвлзуся передо связей ггхптсскич :оэд;'51лП1:й, таепцях плхллослчеслоо строскко, по; тег,;;/ с.чк ■лло оллч ллл лул:глт:;лго гг;э,т:с7£Гзло:п1Я плрокого круга 'ллллл'лолгльлл ^ллх соуДиУЛ'Л!. В егчз-т с st¡"1 использовала лллеллрлфово;! молелн /дл продсталлстлтя лолелул с делока-1 гльсгоцсптрс-й^л езлзягли л разработка методов

•¡ОрлСстлл у.оллкуллрпих r.íneprpacpoB является актуальной зллачеЛ.

Целью работ! • являотся рэзэсЗстка сбдего подхода я фор-•лгровэнн:) инвариантов графой л гппергряфоз, однозначно ха-эзктбтшукаих отдолыпо класса х-дллчес.чпл соедккошй.

Ит/тная новизна, в работе предлогзла juiacraataxaiaifl инвариантов грофов. Показано, что основой построения чпелоншп жтардаятов являются структурен:? инварианта гргфа. Для под-

графов правильных шестиугольной и четырехугольной решеток найден полный структурный инвариант - множество граничных . вершин - и на его основе создан полный численный инвариант - . граничная степенная последовательность. РазреОотан и прог-- : раммно реализован алгоритм генерации полицкклических графов.

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

Предложен новый подход к созданию составных инвариантов-молекуляршх графов - топологических спектров и показано их использование для установления спектро-структурных корреляций. Перспективность предложенного подхода подтверждается наличием линейных корреляционных зависимостей между информационными индексами топологических спектров и масс-спектров металлоорганических соединений.

Практическая значимость. Разработанный пакет прикладных программ "Анализ структурной химической информации", в рамках которого осуществляется компьютерный анализ молекулярных графов и молекулярных гиперграфов, используется в Институте элемэнтоорганических соединений им.А.Н.Несмеянова РАН и в Государственном института усовершенствования врачей, г.Новокузнецк, что подтверждается актами о внедрении.

Работа выполнена в рамках программы фундаментальных исследований СО 03.03 "Химическая информатика".

Апробация работы и публикации. Основные результаты диссертации докладывались на VII и VIII Всесоюзных конференциях "Использование вычислительных машин в спектроскопии молекул и химических исследованиях" (г.Рига, 1936г..г.Новосибирск, 1989г.); на Всесоюзном рабочем совещании "Компьютерная химия" (г.Иркутск, 1988г.); на IV Всесоюзном совещании "Методы и программы решения оптимизационных задач на графах и сетях" (г.Новосибирск, 1989г.); на Уежвуоовской конференции "Молекулярные графы в химических исследованиях (г.Тверь, 1990г.); на IX .Всесоюзной конференции ' "Химическая информатика" (г.Черноголовка, 19Э2г.); на научных семинарах Института математики 00 РАН, Института органической химии мл. Н.Д.Зелинского РАК, Института эйемонтоорганичоских соединений им. А.Н.Несмеянова РАН.

По материалам диссертации опубликовано 10 научных работ, из них 8 статей.

Структура работы. Диссертация состоит из введения, трех глав, заключения и пяти приложений, изложена на 112 страницах. содержит 34 рисунка и список литературы, состоящий из 31 наименования. Общий объем работы 165 страниц.

СОДЕРЖАНИЕ РАБОТЫ

Введите обосновывает актуальность выбранной темы, определяет мели и задачи исследования, структуру работы.

г. гюрзой главе рассматриваются инварианта обыкновенных rpa'f.oc и дается их классификация. Основой классификации является обобщенное определение инварианта графа, введенное в :г.г.агра.£о. Ка его основе определены простой и состав-.

j:o.'ï, д c'j'r;y:c?.',";iïjii, дола.лл:ШР л rivroaa/j.M-u.uu, к:.--

аохлчеахл:: v. локагиьл-;ОСл1': , u лололлаа

пхдд,. Oc;o5oa -дхмалла удолл.лсн стр:л:'Д/рл;л,: лл;арлалал:, лоторпо лпллигол ochobcî: лослрллкя чижxi'!>r жварилплал. Во втором пар^грй.; = лолазадз одгхшш&льшм' ос&с!. сгруггуг»-ичх и чло;:оШ1Дх iB'-r.nitaiJïOS. К^оомоарзю! ^згочзздг.ацде upit-î.x'bu Tavxi овяз;:. Сличена, что усплл i:d:i пестроо;л:х "xo.o-niera" члолашголо -¡¡лзарлалла a:iui;ciiï от лралиллдого лллор: слрултурлого пяварланта. от ';oro наотхшлл) г аде рла то льни: i/оояаднла ладл.-лсл. P двух лрелаяя-ллкл' кал-ал

пне б j.'i:vtip.')5'yss ^лслсхпаа цлларлад >х; оРхкновз;ли}. лра;уои 1 тэло.'Хпглоалл; ^лдадсл лраров ' полазала

овлов оо с; г ! »v 'vt.v] ч"-".-j* вилгрххл'халл.

В Tpe'VbG'ù Параграфе ПрЛВЛ.ДГТСЛ OÙSOp ДЛВЛрЛЛН'ТЛ;-з, осно вакилх ла xiapopuauxoiLUa;.: ло,чходз. Озлочаился, что даиад подход ллохупаоз в р )лх уялворза i^MOi'O алнлз а^оаллл ;лгл чзскш: совдх^олд: и их гслз:,уллрпхх градов. Ср;плл вз -в дословное :!1'j;hotoî; вовлолхоот:. дордзлядлоийово алал,;за рав далта своРозв хвлиа ¡cxibx caapaioiuBl в одллор яхщвшсгв^вво Кал правила, ааорехлхо-лл^орлзлдоаялв ввдокоп оррллл. ют ¡,;apy с.полвол'вл ваол cvp.;. то воль льлллхлл лхлзг

ральдн;.П! хлдскоала. ?> ра.Ротз врод^лллстр^грсвала аозмзл.лас-л прххзв^лля в:в;овлвллол;.аво аолхсдл для полтросдвл.! ii: хард ¡¡г. с;гhbx лодалвлш. (ворлвплхх; влдоксов. Ua озвовв нроллз; ¡лЦорхацлопних ьлрлллдях wi:',vkcol- получеш п:тогра;лл1Лл ¡и фогмзцвошшэ яндокси, чувош-полшосгъ которых да ro..,ocvj пожидшшхчоиз;^ структур ксслсдошвя во сторож главе.

В четвертом параграфе дан обзор составных инвариантов графов и предложен новый подход к построению составных ива-ригнтов - топологических спектров, основаньях на локальной характеркзации отдельных ойемеитов графа. Введено понятие п-мерного токологического спектра к рассмотрены примеры построения '¿-мерных спектров. Показано использование нотах инвариантов ир;х установлении спекасо-струкгуршх корреляция.

Топологические спектры с определенней степень» пряохя-хкиял позголяте описывать строение молекулгонш графов.Масс-спектры тзкжо воссоздают щкбдгаенную картину строения и реакционной способности молекул, отражал "поведение" некоторых ео фрагментов, которые жзю интерпретировать кок под» гра^н молекулярных графов. Для оценки связи тспологпчосчах спектров и характеристик масс-спектра нспольсовале.ч пнформа ■ 15юнпнй подход, кстор,:'1, как отмечалось гете, дает боскок-ность проводить колячястЕеюшй авапз различных способов ¡гредставлекпя химической структуры и позволяющий сравнивать .их в единой икале.

На примере соря производных ферроцбнй' показано, что между топологическими спектрами их молекулярных графов и масс-спектрами ¡имеются коррелящклпшэ зависимости' (коэффициент корреляции г рассматриваемых случаях меняется от 0.80 до 0.97). На основе продло:кешюге подхода получены аналогичные результаты в [Некрасов и др.,1992] для серии арклеиланов, содержащих метильные, вглшльшо и аллилышв группу.

Данный подход поиска спектро-структурнш: корреляций позволяет, с одной стороны, исследовать взаимосвязь структура-реакционная способность молекулы, а с другой - является

основой для решения аналитической задачи - установления структуры соединения по его масс-спектру.

Во второй главе изучаются свойства подграфов правильной шестиугольной решетки R°, являющихся молекулярными графами полицикличеоких бензсидных углеводородов, Результаты, полученные для подграфов правильной шестиугольной решетки, обобщаются для подграфов правильной четырехугольной решетки.

В пэрвсм параграфа определяются рассматриваемые классы графов. Граф G, являздийся подграфом R", называется Исб-гра-фом, если ни одна его вершина не является внутренней. Граф G, являющийся подграфом называется pkG-графсм, .ec.raí он содерзккг хотя бы одну внутреннюю вершину, ккб-грэфа описывают ката-конденсированше бензоидные углеводороды, а ркб-графы - пери-конденсировашше баязопднъю углеводорода. Множество ккь-графов и pi:S-графов называют кб-графзмк. Графи гьлшз-нов, которые но являются подграфами IIa и короно-кондексиро-ванше бензоиднне графы, грашща которых состоит из двух или более простых циклов, в класс кб-графов кз попадают.

с использование:,! структурных оеойств правильной шестиугольной решетки доказано следующее утверждение:

■ УТВЕРЖДЕНИЕ. Гренвцц кб-графов G и II ь Н° совпадают тогда л только тогда, когда G и Н (G и I! изоморфны).

Из утверкдения следует, что кб-графы однозначно характеризуются своей границей, то есть множество граничных взр-И1С1 kG-графа является его полным структурным инвариантом.

На основе данного полного структурного инварианта введен -численный инвариант - граничная степенная последователь-

¡гость S(G), определяемая как последовательность степеней грани-шь'х .вершин кб-графа G при заданном направлении обхода и задашгой начальной веришие. Меняя выбор начальной воржпш и ориентацию Rc г южно определить все шсжоство rpomrmux стрпсшидх последовательностей Кб-граФа G, которш соответствуют все возможные ориентированные замкнутые >гар«рутн, пред-сгааяягяйв грряпцу 0 з R". Сводится попятно канонического представления S*(Gi как лексикографически ккнинапыюй гра-нлчной стспзшюй после довагелыгссгл. Доказана следующая

ТЕОГГЗЛя. Пусть ii,Н ость кб-грефы и S*(G),S*(H) ж канонические предстозлглгая. Тогда

<?* (G) - S* ai) « С = Н

!!с теср;мы следуем, что граничная степенная последовательность однозначно харагггерируот кС--графн, т.о. является ;:пх :голп;;м ч'пел^кннм гнаарпантсм.

Пспс&с&пгглп; гра:«лчкоЗ отепошюй последовательности в задачах ucrcicmipBcJi с,бработки кб-графог? является предметом с/едуги.его параграфа. Па основе граничной степенной ¡к«.дадг^атели!сстя предлагается рзввняе таких задач как Босстеловльыго :«тр:;ца яяяюсы графа, определение сякмэт-рий гро^о, генерация графов, визуализация графов. Для кЗ-rpaijten с числом граней 1<h-i3 в таблице 1 представлены результаты машинной генерации. В приложении к диссертации предстагл'.лш изображения всех кб-графов для 1s'M7.

Результат, полученные для подграфов правильной шестиугольной решетки, обобщены в третьем параграфе для подграфов правильной четырехугольной решетки R4. Подграфы R4 спределе-

ТАШШ11А 1. Число кб-графов ci , <0^1^/), внутренними вершинами для КГгЭЗ.

X 0 1 2 о 4 5 6 7 ■ ч 1! с о Грачев

1 1 !

2 1 1

3 2 1 3

4 5 1 1 7

5 12 6 о о 1 22

6 36 24 14 4 3 81

7 118 106 68 25 10 з 1 331

8 411 453 329 144 67 21 9 1 1435

щ аналогично подграфам П° и показана еозмокность их однозначного представления в Еиде граничной степенной последовательности. На основа свойств граничной степенной последовательности реализован алгоритм генерации к4-графов. Приведены результаты генерации к4-графов (1ilrS7) и даны их изображения.

В последнем параграфе второй главы исследована чувствительность 14 топологических и теоретшга-информац'.кяшых индексов на классах кб- и M-графов. Выделено 4 индекса, чувствительность которых на трех рассмотренных множествах графов меняется в ¡гределах от 0.939 до I. Среди них - дез новых теоретико-информационных индекса," введенных в первой главе.

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

Рассмотренные в первых двух 'главах молекулярные графа являются объектом изучения теории обыкновенных rpaiJoB. Однако обыкновенные графы не дают адекватного описания химических соединений неклассического строения. В ¡Бабаев,1987] отмечалось, что существенным недостатком структурной теории

являс-тся отсутствие удобного способа представления молекул с делокализованными -многоцентрэвыми связями. К таким структурам относятся, в частности, металхоорганические"соединения.

3 первом параграфе рассмотрен« основные типы кеталлоор-ганических соединений (HOG) и используемые для их огшсания графовые представления. Отмечены недостатки в представлении МОС обыкновеяшмд графа:,si.

Для описания структур, содержащее долокализованные мяо-гоцентровые связи, во втором параграфа вводится новое графовое представление - .молекулярный гшерграф.

Гиперграф н= (V.tE> состоит из непустого множества вершин V={7. j 1=1.. ..р) и семейства £={Е 13=1.. .q> различных подмножеств множества вершин. Множества Е называют гкгорребрзмн. Степенью ребра Ej гиперграфэ называют множество всех инцидентных ему ворпич! -и обозначают deg В . Ойлшовэтшй гр?ф является частным случаем гиперграфа, в котором для всех ребер Е, 3=1 ...q, dbg Е = 2. -

Гиперграф H=(V,e), представляющий молекулярную структуру F, в котором вершины vev(h) соответствуют отдельным атомам, гиперребра Е е £(Н), степень которых больше двух, соответствуют дехокализованным многоцентровнм связям и гиперреб- ■ pa e<s ie(H)1, deg е = 2, соответствуют обыкновенным ксвэлепт-I2jm связям и отражают структуру лиганда будем называть молекулярным гшерграФом.

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

о

ч

у

а) б) в) г)

Рлс.*!. Молекулярные гипарграфн аллпльного комплекса.

пенью точности представлять молекулярное структуры с делока-ллзсваннпмн многоцентровнул связяуи. Ка примере аллильного комплекса рассмотрен! все его вог.мояаше гкпэрграфовне представления. На рис. 1а) изображен молекулярный гшерграф, в которо;и представлена все делокаллзовакше многонен.ровне сьяги аллильного комплекса. На ряс. 16) представлен молеку-лярин,! гиперграф, в котоххч.5 присутствуют лишь 'гиперрвбрэ, соответствующие в молекулярной структуре связям атома металла с лнгандэм. В расс;л. л-репных типерграфах игнорируется структура лкганда, В случае, есдк имеетзя нообхсдаюсть более детального представления дкгэидэ, кожио рассматривать молекулярные гинергра^и, в которых присутствуют себра, отра-гйвдйу "шутроиш; структуру" лигаш (рис.1в,г). Такой способ списания молекулярных структур гиперграфа'"1 является шобходш;.!км при наличии в металлокомплексах лигандов с одним" к тем же числом атомов углерода, но геста разную структур- -ную формулу.

Третий параграф посвяшон ьопросьм ксотънггорно!» обработки молекулярных структур. В качестве компьютерного представления пшоргрсфа удобно исгользовзть ого матрицу ннциденций,

определяющею гиперграф с точностью до изоморфизма. 5водится понятие капоничесисй матрица шщвденцнй 13'(Н) («акс:ыольквя из всех возмогших р! • qI матриц мшлдегщий) и па ее основе определяется канонический код молекулярного пшзргрьфа. Канонические кодп получаются нз осново простою метода построения канонической мзтрлцц квдддеяцкЯ пшзрграГоЕ.

В алгоритме используется продотаплг.плз птзегрзфп Н в виде двудолы>сго грзро. K(H)=(7,;b,Y), г, котором воркаиц v.eY п Ей е в к (И) смогши тогда и только тогда, когда в н взрллпа ? и ребро Е гсэддеготш. Лкбо.1 копе-wuft гипергрэЗ допускает представление К (Я), ц наоборот,, вгесцкЗ граф К(Н) являемся представлением некоторого конечного пвтерпрафа II и опрздзлязт ого однозначно о точностью до кзоморТасмп.

Оказывается, что приведенная р*я-матрчца crv»:<K:covn R(K(ID) графа К(Н) совпадает по.определению и матоиирГ! видя дс1К.1й гпггреграгра. Тогда, веди определите хапонпчзокул при-ведоплую матрицу сг.'зкиости R* iK(U)) двудольного грзфа К (В) аналогично канонической матрице пнцидеицпа в"(Н) гипзргрзфа II, то взрно СЛсДуЛЛДЗЭ

утвекгдешгё. р.*(к(и)) = в"(Н)

п попов: кшонической матрицы ипциденцвй В* (Н) сводится к поиску кспспической приведенной матрицы смекпостн Н*(К(Н)). Показано, что последняя получается из канонической ггатриаи смз;:;ности графа К(Н) путем простых матричных преобразований.

Алгоритм поиска каношпеской матрицы инциденций гппер-графа включает следующие шаги: -построение графа 1СfII) гиперграфа II; -поиск канонической матриц» смедиости графа К(Н);

-построение приведенной каноитееской матрицы смедшостн графа К(Н). Оценка сложности алгоритма определяется оценкой1 слок-ности алгоритма поиска канонической матрицы смежности?.

Различия, имеющиеся в представлении молекулярных структур оОнкновенними графами и пшерграфами,- отражаются-, на значениях топологических индексов. В четвертом параграфе ириве-де1ш результаты сравнительного анализа некоторых топологических индексов, основанных на расстоянии. Доказано, что для графов и Гиперграфов, являющихся представлением одной и той гке молекулярной структуры, расстояние моаду двумя вершинами молекулярного графа больше или равно расстоянию мекд. теми же вершинами молекулярного гиперграфа. Отсюда,- в частности, следует, что для любой структуры-',, представленной' G и Н, выполняется неравенство W(G>>WCH-), где V/- есть индекс Винера. Аналогичные неравенства выполняются для радиуса и'диаметра.

В четвертом параграфе тею® дан сравнятелы&п'' анализ 23 интегральных топологически и теоретшо-ипформащюшшх индексов для 8 серий молекулярных систем^ тина R-Х,- где R -наиболее распространенные структурные т;шы (лиНоШш&,- раз-ветвлешшо, циклические„ ароматические, гетероциклические, метадлооргаплчеснПе), а; л - на:;5олее распространенные заместители. Для какдоЯ серии исследована чувствительность индексов на обеих моделях, выявлены нескоррелироваишо индексы.

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

vir?' ;; :í!/jl;зллч'л' л; 'л> ,„"д?*:::*:";, Л' ■

-оторл.. л:. глл'лл::! t" л.'">, оол/л:.9 л

сояс лллетлп;. ч: rv :; ..> avfc : лл.-^лл, ¡/ ; .'Л^рг ».'одэлл:

гл лчпоргрп :,Л;.;Л м.олзл:: нлллплйотаг'лл:ло уг^ллчлгль слллл;

•„liojn л.-скорл л'лгрслзллг" пк л; ' >хл :

i ллоллллл ( ') л 1

; структур

Т"

ib.Г

i."" Мб

, .,. ! I р7

р

i

:.7Г г ni г злллгл; • /;:>•;.: л:л,л irixrn ri лл:,

лчтодлгл ллллслси;'.;, лсл-лл л-те:: слл :: л:л:;;з,гллл-лт:^'":,л!ллм1-ллл ллр^сссл ллл ::; ;лтлул1 1 j л л г-,./ку., лтл ' ;>: г; ;ллл гл-.

■ S - л-рлллплльилп осл;л~лле /.ллр.л ;л.лл. п-.иу-

лсллтл? i:

!. Л.ллл: .'.;■:■ ;iг. лллолл "лллл •ллл'^'чллг; ? т'г" ^ л лллл--poil выдолепп слзл'лллю s'i.r плпзр:. гг^ол: лр.ллсД л клр, лолплылР и ллгллллд...; лЛ,г тле, чл-Рг л счл/ктур-Щл, лп-BOBOTsentót il пеклиоллчесллЛ, полпиП и z-.-mMuL. Д<л члеллп-илх л струллуршх л1плл1лл!;т0л покл-сыо лх луклцпеллл: л:т

зависимость.

2. Найдены полные структурный и численный инварианты полицнклических графоЕ, являющихся подграфами правильной шестиугольной и четырехугольной решеток. На основе свойств граничной степенной последовательности предложены алгоритм машинной обработки полициклических градов (восстановление матрицы смежности,.определение симметрии, генерация, визуализация).

3. На-классах полицикличееких графов исследована чувствительность 14 топологических и теоретико -кнфэрма1даошшх индексов. Выделено 4 наиболее чувствительных (от 0.939 до 1), среди которых два новых теоретике-информационных индекса.

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

X '

5. Предложена новая модель представления молекулярных структур с делокаллзовгшнымк много;кентрсЕ1л.;и связями ь< виде молекулярных гшерграфов. Продемонстрированы • различные под ходы к описанию молекулярных структур в раг-ках новей модели.

6. Разработан алгоритм, кансниялции мелекуляг-инх гиперграфов, основанный на'понятии канонической матряш; шкиден -

иий, результатом работы которого является канонический код молекулярного гшерграфа. Канонический код мокет Сыть использован для хранения молекулярных структур в химических базах данных.

7. Для гиперграфовой модели обобщены топологические к теоретико-информационные индекса. Проведен сравнительный анализ индексов графовой и гатергр'афовой моделей для 8 серий молекулярных систем, представленных наиболее распространенными структурными типами и заместителями. Показано, что для всех серий соединений на гиперграфовой модели индексы обладают большей чувствительностью по сравнению с гр"1« -лой моделью. Общее число некоррелированных индексов на г.;лергра-фовой модели выше.

8. Разработана и реализована единая методика компьютерной обработки молекулярных графов и молекулярных гшерграфов в рамках пакета прикладных программ "Анализ структурной химической информации".

Основное содержание диссертации изложено в следующих публикациях:

1. Мжельская Е.В. Графы полициклмческих соединещй//Вопроси алгоритмического анализа структурной информации.-Новоси-.бирск, 1537.-Вып.I19:Вычислительные системы.-С.71-90.

2. Мжельская Е.В. Подграф* правильной четырехугольней реке тки Н4//Алгорптмнческий анализ графов и его применения. -Новосибирск, 1988. -Вып. 127: ¡Вычислительные системы. -С. 143151.

3. Мжельская В.В..Скоробогатов В.А. Метрические спектры мо-

.;/..::7.'„;j-v ч. ' /liv-ï.ï.;.;,.;e r:J.-KoEoe;;Oi;Ho:„,

1900.-1::т ocliic, вопроси татской пщо:-;„а~

Tji п. G.су я;,.

Ko::cvdu:""jï"-.c й.В. .Iisjxís л.л. о %глтвлте лыюсти икфо},-мащ'с:,;1!:;;. • тсис.чо; ачсспк; .скоав лолкцйхлкчоских гра-iior//f.'.bv-s:^iv.riec<J!c ассдзд-л. ':ыа в ьшичеехой информат:-:-ко.-Новоепг.прок, I95i .-::t;ri. !съ:Ьич«сж:авлышо сиоташ.-С.ье-43.

â. Скороб0Г£к>п B.«í.Констлитиа-.^а К.Е. Г'пгерграфы молекул с лодкалкодашогс: хз»ого!1-э:к-ошглк срясякк/Л'сз. докл. м ^азузсгс.^-'Я кокф.'реьцли " '.V,-.екулкркие грары в хя лчес-кеследлоаллях",!Сал;пл:н! 1990. -Кшгвш,1990.-С.&0. !-:uti(.?nimn¡oijo E.U. /Зкорабог;.;::л в.л. Структурние п чис-

vaa-spria'TTH с.';!:кисвзк:п/ молекулярьих графов// î-.:itc. - ni мето;д, в м-мпчегкой пнформат;:ке.-Коьосп-

v;;p'.4M 199 . -tun. i 'iO;BU4vic ис;вшв систему. - С.В7-129. .'loopuí-aní .А, .Консганткноза .й. Д'.еГгрмакова ü.M. .Палеев Л.Л.,Скор'.._"or атоз .i.A. Проггямкй&й кохплс'кс МйТАШ //Матзматкч^сокко цо&ждогла'.'./; в химической ¡шфэрмзтике. НотеосиСпрек, 1991 .-Ei.n. !36:Lu длительные CKCTWi.-C.d-i5

8. Slrorobogalov V.¿. .Konstantin: va E. Y. .Ilekrasov Yu.S. ,So/.-ï.srsv lu.l'i., Tepier E.K. 0r¡ ihe corrolaf on between the molecular Information topological ana лаоs-spectra indices oí „crganoreetalllc conpcurcfc// fía i h. Oher:1.. (HATCH) 199! .- J&C. -P.215-228.