Abstract
Comparing vertebrate genomes requires efficient cross-species sequence alignment programs. We describe COMBAT, a new mer-based method which can search rapidly for highly similar translated genomic sequences, with the stable-marriage algorithm with incomplete lists (SMI) as a filter scheme. We apply the COMBAT program to the comparative analysis of the human with the most recent bovine genome assemblies, and 84%~95% of the homologous blocks identified by this program are confirmed by BLASTZ.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Pachter, L., Mesirov, J.P., Berger, B., Batzoglou, S., Lander, E.S.: Human and mouse gene structure: Comparative analysis and application to exon prediction. Genome Res., 950–958 (2000)
Bray, N., Dubchak, I., Pachter, L.: Avid: A global alignment program. Genome Res., 97–102 (2003)
Brudno, M., Do, C.B., Cooper, G.M., Kim, M.F., Davydov, E.D.: Lagan and multi-lagan: Efficient tools for large-scale multiple alignment of genomic dna. Genome Res., 721–731 (2003)
Delcher, A.L., Kasif, S., Fleischmann, R.D., Peterson, J., White, O., Salzberg, S.L.: Alignment of whole genomes. Nucleic Acids Res., 2369–2376 (1999)
Frazer, K.A., Elnitski, L., Church, D.M., Dubchak, I., Hardison, R.C.: Cross-species sequence comparisons: A review of methods and available resources. Genome Res., 1–12 (2003)
Gale, D., Shapley, L.S.: College admissions and the stability of marriage. Am. Math. Monthly, 9–15 (1962)
Kent, W.J.: Blat - the blast-like alignment tool. Genome Res. (4), 656–664 (2002)
Morgenstern, B., Rinner, O., Abdeddaöm, S., Haase, D., Mayer, K.F.X., Dress, A.W.M., Mewes, H.W.: Exon discovery by genomic sequence alignment. Bioinformatics (6), 777–787 (2002)
Schwartz, S., Kent, W.J., Smit, A., Zhang, Z., et al.: Human-mouse alignments with blastz. Genome Res., 103–107 (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Sun, B., Schwartz, J.T., Gill, O.H., Mishra, B. (2006). COMBAT: Search Rapidly for Highly Similar Protein-Coding Sequences Using Bipartite Graph Matching. In: Alexandrov, V.N., van Albada, G.D., Sloot, P.M.A., Dongarra, J. (eds) Computational Science – ICCS 2006. ICCS 2006. Lecture Notes in Computer Science, vol 3992. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11758525_89
Download citation
DOI: https://doi.org/10.1007/11758525_89
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-34381-3
Online ISBN: 978-3-540-34382-0
eBook Packages: Computer ScienceComputer Science (R0)