Algorithms for comparing large pedigree graphs

Nahla A. Belal, Lamiaa A. Amar, Hany H. Sherief

Abstract


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.

Keywords


Pedigree Graphs; Isomorphism; Parameterized Algorithm; Kernelization Algorithms

Full Text:

PDF

References


D. He, Z. Wang, E. Eskin, “Iped2: Inheritance path based pedigree reconstruction algorithm for complicated pedigrees,” IEEE/ACM Trans. Comput. Biol. Bioinformatics, Vol.14, issue no 5, pp.1094-1103, September 2017.

M. Ghimiray, R . Vernooy.”The importance and challenges of crop germplasm interdependence: the case of Bhutan,” Food Secur. Vol. 9, pp.301-310. April 2017.

TY. Berger-Wolf, SI. Sheikh, et al., “Reconstructing sibling relationships in wild populations,” Bioinformatics, Vol. 23, pp.49-56. 2007.

Brown, DG.; Berger-Wolf, T. Discovering kinship through small subsets, In Algorithms in Bioinformatics; Moulton, V., Singh, M., Eds.; Springer:Berlin, Heidelberg, 2010; pp. 111-123.

Thompson, EA. In Pedigree Analysis in Human Genetics ;Baltimore: Johns HopKins University Press, 1986.

B. Kirkpatrick, SC. Li, RM. Karp, E. Halperin. “Pedigree reconstruction using identity by descent,” J. Comput. Biol. Vol.18, issue no 11, pp.136-152. November 2011.

L. Sun, K. Wilder, MS. McPeek. “Enhanced pedigree error detection,” Hum Hered. Vol.54, issue no 2, pp. 99-110. October 2002.

MS. McPeek, L. Sun. “Statistical tests for detection of misspecied relationships by use of genome screen data,” Am. J. Hum. Genet. Vol.66, issue no 3, pp.1076- 1094. March 2000.

M. Boehnk, NJ. Cox. “Accurate inference of relationships in sib-pair linkage studies,” Am. J. Hum. Genet. Vol.61, issue no 2, pp. 423-429. August 1997.

B. Kirkpatrick, Y. Reshef, H. Finucane, H. Jiang, B. Zhu, RM. Karp. “Comparing pedigree graphs,” J. Comput. Biol. Vol.19, issue no 9, pp. 998-1014. October 2012.

Z. Chen, Q. Feng, C. Shen, J. Wang, L. Wang. “Algorithms for pedigree comparison,” IEEE/ACM Trans. Comput. Biology Bioinform, Vol.15, issue no 2, pp. 422-431. April 2018.

CM. Herbinger, P. TO’Reilly, RW. Doyle, JM. Wright, F. O’Flynn. “Early growth performance of Atlantic salmon full-sib families reared in single family tanks versus in mixed family tanks,” Aquaculture, Vol.173, issue no 14, pp. 105-116. March 1999.

H. Jiang, G. Lin, W. Tong, D. Zhu, B.Zhu. “Isomorphism and similarity for 2- generation pedigrees,” BMC Bioinformatics, Vol.16, issue no Suppl(5), pp. 1-8. March 2015.

LA. Amar, NA. Belal, S. Rashwan. “Comparing unlabeled pedigree graphs via covering with bipartite and pat,” J. Comput. Biol. Vol.23, issue no 11, pp. 912- 922. November 2016.

Braun, Bremen L and Schott, David A and Portwood, John L and Andorf, Carson M and Sen, Taner Z. “PedigreeNet: a web-based pedigree viewer for biological databases,” Bioinformatics, 35(20), pp. 4184-4186 October 2019.

N. Xie, Q. Sun, J. Yang, Y. Zhou, H. Xu, L. Zhou, Y. Zhou. “High clinical heterogeneity in a Chinese pedigree of retinal vasculopathy with cerebral leukoencephalopathy and systemic manifestations (RVCL-S),” Orphanet Journal of Rare Diseases,16(1), pp.1-15, Jan 2021.

H. Yu, G.Morota. “GCA: an R package for genetic connectedness analysis using pedigree and genomic data,” BMC Genomics, 22(119), pp.1-8, February 2021.

Z.J. Rawandoozi, T.P. Hartmann, S. Carpenedo, K. Gasic, et al., “Mapping and characterization QTLs for phenological traits in seven pedigree-connected peach families,” BMC Genomics, 22(187), pp.1-16, March 2021.

J. You, J. Wang, Q. Feng, F. Shi. “Kernelization and parameterized algorithms for covering a tree by a set of stars or paths,” Theor. Comput. Sci. Vol 607, part 2, pp. 257-270. November 2015.

J. Baumbach, J.Guo, R. Ibragimov. “Covering tree with stars,” In: Computing and Combinatorics.;19th International Conference; COCOON; Springer: Hangzhou, China, 2013.

J. Chen, IA. Kanj, W. Jia. “Vertex cover: Further observations and further improvements,” J. Algorithms, Vol.41, issue no 2, pp. 280-301. November 2001.




DOI: http://dx.doi.org/10.21622/ace.2022.02.1.043

Refbacks

  • There are currently no refbacks.


Copyright (c) 2022 Nahla A. Belal, Lamiaa A. Amar, Hany H. Sherief

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.


Advances in Computing and Engineering
E-ISSN: 2735-5985
P-ISSN: 2735-5977

Published by:

Academy Publishing Center (APC)
Arab Academy for Science, Technology and Maritime Transport (AASTMT)
Alexandria, Egypt
ace@aast.edu