[논문]A Metabolic Pathway Drawing Algorithm for Reducing the Number of Edge Crossings

Song Eun-Ha; Kim Min-Kyung; Lee Sang-Ho

A Metabolic Pathway Drawing Algorithm for Reducing the Number of Edge Crossings 원문보기

Genomics & informatics, v.4 no.3, 2006년, pp.118 - 124

Song Eun-Ha (Department of Computer Science and Engineering, Ewha Womans University) , Kim Min-Kyung (UC Irvine Institute for Genomics and Bioinformatics) , Lee Sang-Ho (Department of Computer Science and Engineering, Ewha Womans University)

Abstract ▼ AI-Helper

For the direct understanding of flow, pathway data are usually represented as directed graphs in biological journals and texts. Databases of metabolic pathways or signal transduction pathways inevitably contain these kinds of graphs to show the flow. KEGG, one of the representative pathway databases, uses the manually drawn figure which can not be easily maintained. Graph layout algorithms are applied for visualizing metabolic pathways in some databases, such as EcoCyc. Although these can express any changes of data in the real time, it exponentially increases the edge crossings according to the increase of nodes. For the understanding of genome scale flow of metabolism, it is very important to reduce the unnecessary edge crossings which exist in the automatic graph layout. We propose a metabolic pathway drawing algorithm for reducing the number of edge crossings by considering the fact that metabolic pathway graph is scale-free network. The experimental results show that the number of edge crossings is reduced about $37{\sim}40%$ by the consideration of scale-free network in contrast with non-considering scale-free network. And also we found that the increase of nodes do not always mean that there is an increase of edge crossings.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

The experimental results are very similar to common structure of metabolic pathway as compared with layout 「es니Its in the previous systems it is possible to assi오t understanding of biological researchers. In contrast to visualize only a single pathway in previous layout system, our layout algorithm is possible to visualize multi pathways simultaneously.

제안 방법

Experiments were performed by two algorithms with metabolic pathways in KEGG as test data. Then we compared with thenurnber of edge crossings for two layout「es 냐]ts.
In this paper, we described the metabolic pathway drawing algorithm based on ascale-free network structural characteristic and analyzed the algorithm from viewpoint of the number of edge crossings.
pyruvate, as shown in Table 1. Therefore new methods are needed for reducing edge crossing drastically or new module should be added to pathway layout algorithm for abstracting it in order to simplify the topology of the given graph. Hence, we now research a new method that finds highly connected subgraphs existing in a pathway graph, i.

성능/효과

The experimental results show that the number of edge crossings is reduced about 37~40% as the number of nodes increases in pathway graph in contrast with non-considering scale-free network. Therefore, it is possible to red니ce unnecessary edge crossings by considering the facts that metabolic pathway graph is scale-free network.

참고문헌 (11)

Barabasi, A.L. and Albert, R. (1999). Emergence of Scaling in Random Networks. Science 286, 509-512

상세보기
Becker, M.Y. and Rojas, I. (2001). A Graph Layout Algorithm for Drawing Metabolic Pathways. Bioinformatics 17, 461-467

상세보기
BioCarta Team. (2001). Biocarta: Charting Pathways of Life. http://www.biocarta.com
Goh, K.I., Kahng, B., and Kim, D. (2001). Universal Behavior of Load Distribution in Scale-Free Networks. Physical Review Letters 87, 278701

상세보기
Holme, P., Huss, M., and Jeong, H. (2003). Subnetwork Hierarchies of Biochemical Pathways. Bioinformatics 19, 532-538

상세보기
Jeong, H., Tombor, B., Albert, R., Oltvai, Z.N., and Barabasi, A.L. (2000). The Large-scale Organization of Metabolic Networks. Nature 407, 651-654

상세보기
Kanehisa, M., Goto, S., Kawashima, S., and Nakaya, A. (2002). The KEGG Databases at GenomeNet. Nucleic Acids Res. 30, 42-46

상세보기
Karp, P.D. and Paley, S. (1994). Automated Drawing of Metabolic Pathways. Third International Conference on Bioinformatics and Genome Research. 225-238
Karp, P.D., Riley, M., Saier, M., Paulsen, I.T., Collado-Vides, J., Paley, S.M., Pellegrini-Toole, A., Bonavides, C., and Gama-Castro, S. (2002). The EcoCyc Database. Nucleic Acids Res. 30, 56-58

상세보기
Lee, S.H., Song, E.H., Lee, S.H., and Park, H.S. (2004). An Algorithm for Drawing Metabolic Pathways based on Structural Characteristics, J. Korea Information Science Society 31, 1266-1275
Wiese, R., Eiglsperger, M., and Schabert, P. (2000). The Y-files Graph Library: Documentation and Code. http://www-pr.informatik.uni-tuebingen.de/yfiles

원문 보기

ScienceON 원문보기

원문 URL 링크

한국유전체학회 : 저널

*원문 PDF 파일 및 링크정보가 존재하지 않을 경우 KISTI DDS 시스템에서 제공하는 원문복사서비스를 사용할 수 있습니다.

내보내기 메뉴

내보내기 구분

파일저장
인쇄
메일전송

구성항목

기본정보
상세정보

관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관

저장형식

Text(ASCII format)
Excel format
RefWorks Direct Export
RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley

메일정보

받는사람 (필수): @
보내는사람 (선택): @
제목
내용: KISTI 검색결과 이메일 서비스

안내

총 건의 자료가 검색되었습니다.

다운받으실 자료의 인덱스를 입력하세요. (1-10,000)

검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다.

데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요)

다운로드 파일은 UTF-8 형태로 저장됩니다.
파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오.

Text(ASCII format)
Excel format

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

AI-Helper ※ AI-Helper는 을 사용합니다.

AI-Helper

안녕하세요, AI-Helper입니다. 좌측 "선택된 텍스트"에서 텍스트를 선택하여 요약, 번역, 용어설명을 실행하세요.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.

연합인증