<?xml version="1.0"?>
<?xml-stylesheet type="text/css" href="http://metabolomics.jp/mediawiki/skins/common/feed.css?303"?>
<feed xmlns="http://www.w3.org/2005/Atom" xml:lang="en">
		<id>http://metabolomics.jp/mediawiki/index.php?action=history&amp;feed=atom&amp;title=Aritalab%3ALecture%2FAlgorithm%2FRingDetection</id>
		<title>Aritalab:Lecture/Algorithm/RingDetection - Revision history</title>
		<link rel="self" type="application/atom+xml" href="http://metabolomics.jp/mediawiki/index.php?action=history&amp;feed=atom&amp;title=Aritalab%3ALecture%2FAlgorithm%2FRingDetection"/>
		<link rel="alternate" type="text/html" href="http://metabolomics.jp/mediawiki/index.php?title=Aritalab:Lecture/Algorithm/RingDetection&amp;action=history"/>
		<updated>2026-04-09T00:20:26Z</updated>
		<subtitle>Revision history for this page on the wiki</subtitle>
		<generator>MediaWiki 1.19.1</generator>

	<entry>
		<id>http://metabolomics.jp/mediawiki/index.php?title=Aritalab:Lecture/Algorithm/RingDetection&amp;diff=254263&amp;oldid=prev</id>
		<title>Adm at 16:00, 1 June 2011</title>
		<link rel="alternate" type="text/html" href="http://metabolomics.jp/mediawiki/index.php?title=Aritalab:Lecture/Algorithm/RingDetection&amp;diff=254263&amp;oldid=prev"/>
				<updated>2011-06-01T16:00:48Z</updated>
		
		<summary type="html">&lt;p&gt;&lt;/p&gt;
&lt;table class='diff diff-contentalign-left'&gt;
				&lt;col class='diff-marker' /&gt;
				&lt;col class='diff-content' /&gt;
				&lt;col class='diff-marker' /&gt;
				&lt;col class='diff-content' /&gt;
			&lt;tr valign='top'&gt;
			&lt;td colspan='2' style=&quot;background-color: white; color:black;&quot;&gt;← Older revision&lt;/td&gt;
			&lt;td colspan='2' style=&quot;background-color: white; color:black;&quot;&gt;Revision as of 16:00, 1 June 2011&lt;/td&gt;
			&lt;/tr&gt;&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-lineno&quot;&gt;Line 23:&lt;/td&gt;
&lt;td colspan=&quot;2&quot; class=&quot;diff-lineno&quot;&gt;Line 23:&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class='diff-marker'&gt;&amp;#160;&lt;/td&gt;&lt;td style=&quot;background: #eee; color:black; font-size: smaller;&quot;&gt;&lt;div&gt;#各サイクルについて、&amp;amp;pi;電子が(4n + 2)個になるか検証&lt;/div&gt;&lt;/td&gt;&lt;td class='diff-marker'&gt;&amp;#160;&lt;/td&gt;&lt;td style=&quot;background: #eee; color:black; font-size: smaller;&quot;&gt;&lt;div&gt;#各サイクルについて、&amp;amp;pi;電子が(4n + 2)個になるか検証&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class='diff-marker'&gt;&amp;#160;&lt;/td&gt;&lt;td style=&quot;background: #eee; color:black; font-size: smaller;&quot;&gt;&lt;/td&gt;&lt;td class='diff-marker'&gt;&amp;#160;&lt;/td&gt;&lt;td style=&quot;background: #eee; color:black; font-size: smaller;&quot;&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class='diff-marker'&gt;−&lt;/td&gt;&lt;td style=&quot;background: #ffa; color:black; font-size: smaller;&quot;&gt;&lt;div&gt;&lt;del class=&quot;diffchange diffchange-inline&quot;&gt;=&lt;/del&gt;===プログラムを実装する上での問題点&lt;del class=&quot;diffchange diffchange-inline&quot;&gt;=&lt;/del&gt;===&lt;/div&gt;&lt;/td&gt;&lt;td class='diff-marker'&gt;+&lt;/td&gt;&lt;td style=&quot;background: #cfc; color:black; font-size: smaller;&quot;&gt;&lt;div&gt;===プログラムを実装する上での問題点===&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class='diff-marker'&gt;&amp;#160;&lt;/td&gt;&lt;td style=&quot;background: #eee; color:black; font-size: smaller;&quot;&gt;&lt;/td&gt;&lt;td class='diff-marker'&gt;&amp;#160;&lt;/td&gt;&lt;td style=&quot;background: #eee; color:black; font-size: smaller;&quot;&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class='diff-marker'&gt;&amp;#160;&lt;/td&gt;&lt;td style=&quot;background: #eee; color:black; font-size: smaller;&quot;&gt;&lt;div&gt;n点の平面グラフでも、サイクルの数は2.2nより大きくなりうることが知られている (Alt, H. Fuchs, U. Kriegel, K. Combinatorics, Probability and Computing 8:397-405, 1999)。つまり、全てのサイクルを検証していると指数時間かかってしまう。しかし、全てのサイクルの基底をなすサイクル集合を見つけることは容易でないし、当然だが基底も一意ではない(Horton, JD. SIAM Journal on Computing, 16(2):358-366, 1987)。&lt;/div&gt;&lt;/td&gt;&lt;td class='diff-marker'&gt;&amp;#160;&lt;/td&gt;&lt;td style=&quot;background: #eee; color:black; font-size: smaller;&quot;&gt;&lt;div&gt;n点の平面グラフでも、サイクルの数は2.2nより大きくなりうることが知られている (Alt, H. Fuchs, U. Kriegel, K. Combinatorics, Probability and Computing 8:397-405, 1999)。つまり、全てのサイクルを検証していると指数時間かかってしまう。しかし、全てのサイクルの基底をなすサイクル集合を見つけることは容易でないし、当然だが基底も一意ではない(Horton, JD. SIAM Journal on Computing, 16(2):358-366, 1987)。&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;/table&gt;</summary>
		<author><name>Adm</name></author>	</entry>

	<entry>
		<id>http://metabolomics.jp/mediawiki/index.php?title=Aritalab:Lecture/Algorithm/RingDetection&amp;diff=254262&amp;oldid=prev</id>
		<title>Adm: Created page with &quot;==化学構造における芳香環==  ===芳香環の定義===  芳香環の実験化学的な定義は、芳香性を持つ平面状の共役環状構造となります。共...&quot;</title>
		<link rel="alternate" type="text/html" href="http://metabolomics.jp/mediawiki/index.php?title=Aritalab:Lecture/Algorithm/RingDetection&amp;diff=254262&amp;oldid=prev"/>
				<updated>2011-06-01T16:00:18Z</updated>
		
		<summary type="html">&lt;p&gt;Created page with &amp;quot;==化学構造における芳香環==  ===芳香環の定義===  芳香環の実験化学的な定義は、芳香性を持つ平面状の共役環状構造となります。共...&amp;quot;&lt;/p&gt;
&lt;p&gt;&lt;b&gt;New page&lt;/b&gt;&lt;/p&gt;&lt;div&gt;==化学構造における芳香環==&lt;br /&gt;
&lt;br /&gt;
===芳香環の定義===&lt;br /&gt;
&lt;br /&gt;
芳香環の実験化学的な定義は、芳香性を持つ平面状の共役環状構造となります。共役構造とは、炭素の場合、単結合と二重結合が交互に現れる状態です。炭素のほかにも窒素、酸素、硫黄が芳香環を作れます。&lt;br /&gt;
&lt;br /&gt;
芳香環は(4n + 2)個の&amp;amp;pi;電子を持つことが知られています(Hueckel rule)。環上の各原子が供与する&amp;amp;pi;電子の数は以下のように決まります。&lt;br /&gt;
&lt;br /&gt;
*二重結合をもつ炭素、窒素、酸素、硫黄なら１個&lt;br /&gt;
*二重結合を持たない窒素、酸素、硫黄なら２個&lt;br /&gt;
&lt;br /&gt;
したがって、以下に示す物質はいずれも芳香環になります。あまり言われませんが、DNAの塩基は芳香環なのです。（だから平面構造をしています。）&lt;br /&gt;
{| class=&amp;quot;wikitable&amp;quot;&lt;br /&gt;
|- valign=&amp;quot;top&amp;quot;&lt;br /&gt;
| benzene&amp;lt;br/&amp;gt;[[File:benzene.png]] || adenine&amp;lt;br/&amp;gt;[[File:adenine.png]] || cytosine&amp;lt;br/&amp;gt;[[File:cytosine.png]] || pyrazole&amp;lt;br/&amp;gt;[[File:pyrazole.png]] || imidazole&amp;lt;br/&amp;gt;[[File:imidazole.png]]&lt;br /&gt;
|}&lt;br /&gt;
&lt;br /&gt;
===芳香環の検出===&lt;br /&gt;
&lt;br /&gt;
ベンゼン環などの芳香環を単結合と二重結合の並びで記述すると、同一構造を一見、異なった形に描けてしまいます。化学構造中における芳香環の検出は、構造を正規化したり、構造における対称部分を見出すためにも必須の基本操作です。分子構造をグラフと考えると、芳香環の検出は以下のステップで達成できます。&lt;br /&gt;
&lt;br /&gt;
#グラフ（構造）中の全てのサイクルを検出&lt;br /&gt;
#各サイクルについて、&amp;amp;pi;電子が(4n + 2)個になるか検証&lt;br /&gt;
&lt;br /&gt;
====プログラムを実装する上での問題点====&lt;br /&gt;
&lt;br /&gt;
n点の平面グラフでも、サイクルの数は2.2nより大きくなりうることが知られている (Alt, H. Fuchs, U. Kriegel, K. Combinatorics, Probability and Computing 8:397-405, 1999)。つまり、全てのサイクルを検証していると指数時間かかってしまう。しかし、全てのサイクルの基底をなすサイクル集合を見つけることは容易でないし、当然だが基底も一意ではない(Horton, JD. SIAM Journal on Computing, 16(2):358-366, 1987)。&lt;br /&gt;
&lt;br /&gt;
例えば、ヘム環の外周は芳香環である。しかしこれを迅速に検出する汎用アルゴリズムの設計は上記の理由で難しい。計算化学の世界では実にさまざまなヒューリスティックが提唱されているが、いずれも理論的には抜け穴が多い。芳香環検出が難しい「困った」化合物の例を２つだけ挙げておく。&lt;br /&gt;
&lt;br /&gt;
{| class=&amp;quot;wikitable&amp;quot;&lt;br /&gt;
|- valign=&amp;quot;top&amp;quot;&lt;br /&gt;
| Heme O&amp;lt;br/&amp;gt;[[File:heme.png]] || adenosyl cobalamin&amp;lt;br/&amp;gt;[[File:cobalamin.png]]&lt;br /&gt;
|}&lt;/div&gt;</summary>
		<author><name>Adm</name></author>	</entry>

	</feed>