Kavosh: a new algorithm for finding network motifs
<p>Abstract</p> <p>Background</p> <p>Complex networks are studied across many fields of science and are particularly important to understand biological processes. Motifs in networks are small connected sub-graphs that occur significantly in higher frequencies than in ra...
| Main Authors: | , , , , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
BMC
2009-10-01
|
| Series: | BMC Bioinformatics |
| Online Access: | http://www.biomedcentral.com/1471-2105/10/318 |
| _version_ | 1818790856730083328 |
|---|---|
| author | Asadi Sahar Ansari Elnaz Nowzari-Dalini Abbas Elahi Elahe Ahrabian Hayedeh Kashani Zahra Mohammadi Shahin Schreiber Falk Masoudi-Nejad Ali |
| author_facet | Asadi Sahar Ansari Elnaz Nowzari-Dalini Abbas Elahi Elahe Ahrabian Hayedeh Kashani Zahra Mohammadi Shahin Schreiber Falk Masoudi-Nejad Ali |
| author_sort | Asadi Sahar |
| collection | DOAJ |
| description | <p>Abstract</p> <p>Background</p> <p>Complex networks are studied across many fields of science and are particularly important to understand biological processes. Motifs in networks are small connected sub-graphs that occur significantly in higher frequencies than in random networks. They have recently gathered much attention as a useful concept to uncover structural design principles of complex networks. Existing algorithms for finding network motifs are extremely costly in CPU time and memory consumption and have practically restrictions on the size of motifs.</p> <p>Results</p> <p>We present a new algorithm (Kavosh), for finding k-size network motifs with less memory and CPU time in comparison to other existing algorithms. Our algorithm is based on counting all k-size sub-graphs of a given graph (directed or undirected). We evaluated our algorithm on biological networks of <it>E. coli </it>and <it>S. cereviciae</it>, and also on non-biological networks: a social and an electronic network.</p> <p>Conclusion</p> <p>The efficiency of our algorithm is demonstrated by comparing the obtained results with three well-known motif finding tools. For comparison, the CPU time, memory usage and the similarities of obtained motifs are considered. Besides, Kavosh can be employed for finding motifs of size greater than eight, while most of the other algorithms have restriction on motifs with size greater than eight. The Kavosh source code and help files are freely available at: <url>http://Lbb.ut.ac.ir/Download/LBBsoft/Kavosh/</url>.</p> |
| first_indexed | 2024-12-18T15:02:06Z |
| format | Article |
| id | doaj.art-7908ec50679b447a8d56fee93f5999c6 |
| institution | Directory Open Access Journal |
| issn | 1471-2105 |
| language | English |
| last_indexed | 2024-12-18T15:02:06Z |
| publishDate | 2009-10-01 |
| publisher | BMC |
| record_format | Article |
| series | BMC Bioinformatics |
| spelling | doaj.art-7908ec50679b447a8d56fee93f5999c62022-12-21T21:03:52ZengBMCBMC Bioinformatics1471-21052009-10-0110131810.1186/1471-2105-10-318Kavosh: a new algorithm for finding network motifsAsadi SaharAnsari ElnazNowzari-Dalini AbbasElahi ElaheAhrabian HayedehKashani ZahraMohammadi ShahinSchreiber FalkMasoudi-Nejad Ali<p>Abstract</p> <p>Background</p> <p>Complex networks are studied across many fields of science and are particularly important to understand biological processes. Motifs in networks are small connected sub-graphs that occur significantly in higher frequencies than in random networks. They have recently gathered much attention as a useful concept to uncover structural design principles of complex networks. Existing algorithms for finding network motifs are extremely costly in CPU time and memory consumption and have practically restrictions on the size of motifs.</p> <p>Results</p> <p>We present a new algorithm (Kavosh), for finding k-size network motifs with less memory and CPU time in comparison to other existing algorithms. Our algorithm is based on counting all k-size sub-graphs of a given graph (directed or undirected). We evaluated our algorithm on biological networks of <it>E. coli </it>and <it>S. cereviciae</it>, and also on non-biological networks: a social and an electronic network.</p> <p>Conclusion</p> <p>The efficiency of our algorithm is demonstrated by comparing the obtained results with three well-known motif finding tools. For comparison, the CPU time, memory usage and the similarities of obtained motifs are considered. Besides, Kavosh can be employed for finding motifs of size greater than eight, while most of the other algorithms have restriction on motifs with size greater than eight. The Kavosh source code and help files are freely available at: <url>http://Lbb.ut.ac.ir/Download/LBBsoft/Kavosh/</url>.</p>http://www.biomedcentral.com/1471-2105/10/318 |
| spellingShingle | Asadi Sahar Ansari Elnaz Nowzari-Dalini Abbas Elahi Elahe Ahrabian Hayedeh Kashani Zahra Mohammadi Shahin Schreiber Falk Masoudi-Nejad Ali Kavosh: a new algorithm for finding network motifs BMC Bioinformatics |
| title | Kavosh: a new algorithm for finding network motifs |
| title_full | Kavosh: a new algorithm for finding network motifs |
| title_fullStr | Kavosh: a new algorithm for finding network motifs |
| title_full_unstemmed | Kavosh: a new algorithm for finding network motifs |
| title_short | Kavosh: a new algorithm for finding network motifs |
| title_sort | kavosh a new algorithm for finding network motifs |
| url | http://www.biomedcentral.com/1471-2105/10/318 |
| work_keys_str_mv | AT asadisahar kavoshanewalgorithmforfindingnetworkmotifs AT ansarielnaz kavoshanewalgorithmforfindingnetworkmotifs AT nowzaridaliniabbas kavoshanewalgorithmforfindingnetworkmotifs AT elahielahe kavoshanewalgorithmforfindingnetworkmotifs AT ahrabianhayedeh kavoshanewalgorithmforfindingnetworkmotifs AT kashanizahra kavoshanewalgorithmforfindingnetworkmotifs AT mohammadishahin kavoshanewalgorithmforfindingnetworkmotifs AT schreiberfalk kavoshanewalgorithmforfindingnetworkmotifs AT masoudinejadali kavoshanewalgorithmforfindingnetworkmotifs |