Algorithms for comparing large pedigree graphs
The importance of pedigrees is translated by geneticists as a tool for diagnosing genetic diseases. Errors resulting during collection of data and missing information of individuals are considered obstacles in deducing pedigrees, especially larger ones. Therefore, the reconstructed pedigree graph ev...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Academy Publishing Center
2022-06-01
|
| Series: | Advances in Computing and Engineering |
| Subjects: | |
| Online Access: | http://apc.aast.edu/ojs/index.php/ACE/article/view/474 |
| _version_ | 1797258893382909952 |
|---|---|
| author | Nahla A. Belal Lamiaa A. Amar Hany H. Sherief |
| author_facet | Nahla A. Belal Lamiaa A. Amar Hany H. Sherief |
| author_sort | Nahla A. Belal |
| collection | DOAJ |
| description | The importance of pedigrees is translated by geneticists as a tool for diagnosing genetic diseases. Errors resulting during collection of data and missing information of individuals are considered obstacles in deducing pedigrees, especially larger ones. Therefore, the reconstructed pedigree graph evaluation needs to be undertaken for relevant diagnosis. This requires a comparison between the derived and the original data. The present study discusses the isomorphism of huge pedigrees with labeled and unlabeled leaves, where a pedigree has hundreds of families, which are monogamous and generational. The algorithms presented in this paper are based on a set of bipartite graphs covering the pedigree and the problem addressed is parameter tractable. The Bipartite graphs Covering the Pedigree (BCP) problem is said to possess a time complexity of $f(k).mod(X)^{O(1)}$ where $f$ is the computing function that grows exponentially. The study presents an algorithm for the BCP problem that can be categorized as a polynomial-time-tractable evaluation of the reconstructed pedigree. The paper considers pedigree graphs that consist of both labeled and unlabeled leaves that make use of parameterized and kernelization algorithms to solve the problem. The kernelization algorithm executes in $O(k^3)$ for the BCP graphs. |
| first_indexed | 2024-03-12T01:40:33Z |
| format | Article |
| id | doaj.art-b11f665b22fa4c1dbb1d548cc54a2fdf |
| institution | Directory Open Access Journal |
| issn | 2735-5977 2735-5985 |
| language | English |
| last_indexed | 2024-04-24T23:00:46Z |
| publishDate | 2022-06-01 |
| publisher | Academy Publishing Center |
| record_format | Article |
| series | Advances in Computing and Engineering |
| spelling | doaj.art-b11f665b22fa4c1dbb1d548cc54a2fdf2024-03-17T15:34:15ZengAcademy Publishing CenterAdvances in Computing and Engineering2735-59772735-59852022-06-0121435910.21622/ace.2022.02.1.043204Algorithms for comparing large pedigree graphsNahla A. Belal0Lamiaa A. Amar1Hany H. Sherief2College of Computing and Information Technology, Arab Academy for Science, Technology and Maritime Transport (AASTMT), Smart Village, Giza Arab Academy for Science, Technology, and Maritime TransportAlexandria University, Faculty of Science, Al Azaritah WA Ash Shatebi, Qism Bab Sharqi, AlexandriaAlexandria University, Faculty of Science, Al Azaritah WA Ash Shatebi, Qism Bab Sharqi, AlexandriaThe importance of pedigrees is translated by geneticists as a tool for diagnosing genetic diseases. Errors resulting during collection of data and missing information of individuals are considered obstacles in deducing pedigrees, especially larger ones. Therefore, the reconstructed pedigree graph evaluation needs to be undertaken for relevant diagnosis. This requires a comparison between the derived and the original data. The present study discusses the isomorphism of huge pedigrees with labeled and unlabeled leaves, where a pedigree has hundreds of families, which are monogamous and generational. The algorithms presented in this paper are based on a set of bipartite graphs covering the pedigree and the problem addressed is parameter tractable. The Bipartite graphs Covering the Pedigree (BCP) problem is said to possess a time complexity of $f(k).mod(X)^{O(1)}$ where $f$ is the computing function that grows exponentially. The study presents an algorithm for the BCP problem that can be categorized as a polynomial-time-tractable evaluation of the reconstructed pedigree. The paper considers pedigree graphs that consist of both labeled and unlabeled leaves that make use of parameterized and kernelization algorithms to solve the problem. The kernelization algorithm executes in $O(k^3)$ for the BCP graphs.http://apc.aast.edu/ojs/index.php/ACE/article/view/474pedigree graphsisomorphismparameterized algorithmkernelization algorithms |
| spellingShingle | Nahla A. Belal Lamiaa A. Amar Hany H. Sherief Algorithms for comparing large pedigree graphs Advances in Computing and Engineering pedigree graphs isomorphism parameterized algorithm kernelization algorithms |
| title | Algorithms for comparing large pedigree graphs |
| title_full | Algorithms for comparing large pedigree graphs |
| title_fullStr | Algorithms for comparing large pedigree graphs |
| title_full_unstemmed | Algorithms for comparing large pedigree graphs |
| title_short | Algorithms for comparing large pedigree graphs |
| title_sort | algorithms for comparing large pedigree graphs |
| topic | pedigree graphs isomorphism parameterized algorithm kernelization algorithms |
| url | http://apc.aast.edu/ojs/index.php/ACE/article/view/474 |
| work_keys_str_mv | AT nahlaabelal algorithmsforcomparinglargepedigreegraphs AT lamiaaaamar algorithmsforcomparinglargepedigreegraphs AT hanyhsherief algorithmsforcomparinglargepedigreegraphs |