nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

Alignment of Sequences Allowing for Non-overlapping Unbalanced Translocations of Adjacent Factors

verfasst von : Simone Faro, Arianna Pavone

Erschienen in: Bioinformatics and Biomedical Engineering

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Unbalanced translocations take place when two unequal chromosome sub-sequences swap, resulting in an altered genetic sequence. Such large-scale gene modification are among the most frequent chromosomal alterations, accounted for 30% of all losses of heterozygosity. However, despite of their central role in genomic sequence analysis, little attention has been devoted to the problem of aligning sequences allowing for this kind of modification.

In this paper we investigate the sequence alignment problem when the edit operations are non-overlapping unbalanced translocations of adjacent factors.

Specifically, we present an alignment algorithm for the problem working in \(\mathcal {O}(m^3)\)-time and \(\mathcal {O}(m^3)\)-space, where m is the length of the involved sequences. To the best of our knowledge this is the first solution in literature for the alignment problem allowing for unbalanced translocations of factors.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Image Based Individual Identification of Sumatra Barb (Puntigrus Tetrazona)

Nächstes Kapitel Probability in HPLC-MS Metabolomics

We use the value null to indicate the length of an undefined string in order to discriminate it from the length of an empty string whose value is 0 by definition.

In this context we assume that \(s+\textsf {null} = s\), for any s.

Cantone, D., Cristofaro, S., Faro, S.: Efficient matching of biological sequences allowing for non-overlapping inversions. In: Giancarlo, R., Manzini, G. (eds.) CPM 2011. LNCS, vol. 6661, pp. 364–375. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-21458-5_31CrossRefMATH

Cantone, D., Cristofaro, S., Faro, S.: Efficient string-matching allowing for non-overlapping inversions. Theor. Comput. Sci. 483, 85–95 (2013)MathSciNetCrossRef

Cantone, D., Faro, S., Giaquinta, E.: Approximate string matching allowing for inversions and translocations. In: Proceedings of the Prague Stringology Conference, pp. 37–51 (2010)

Cantone, D., Faro, S., Giaquinta, E.: Text searching allowing for inversions and translocations of factors. Discrete Appl. Math. 163, 247–257 (2014)MathSciNetCrossRef

Cantone, D., Faro, S., Pavone, A.: Sequence searching allowing for non-overlapping adjacent unbalanced translocations. Report arXiv:1812.00421. Cornell University Library (2018). https://arxiv.org/abs/1812.00421

Cho, D.-J., Han, Y.-S., Kim, H.: Alignment with non-overlapping inversions and translocations on two strings. Theor. Comput. Sci. 575, 90–101 (2015)MathSciNetCrossRef

Cull, P., Hsu, T.: Recent advances in the walking tree method for biological sequence alignment. In: Moreno-Díaz, R., Pichler, F. (eds.) EUROCAST 2003. LNCS, vol. 2809, pp. 349–359. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-45210-2_32CrossRef

Damerau, F.: A technique for computer detection and correction of spelling errors. Commun. ACM 7(3), 171–176 (1964)CrossRef

Knuth, D.E., Morris Jr., J.H., Pratt, V.R.: Fast pattern matching in strings. SIAM J. Comput. 6(1), 323–350 (1977)MathSciNetCrossRef

10.

Lupski, J.R.: Genomic disorders: structural features of the genome can lead to DNA rearrangements and human disease traits. Trends Genet. 14(10), 417–422 (1998)CrossRef

11.

Levenshtein, V.I.: Binary codes capable of correcting deletions, insertions and reversals. Sov. Phys. Dokl. 10, 707–710 (1966)MathSciNet

12.

Morris, J.H., Pratt, V.R.: A linear pattern-matching algorithm. Technical report 40. University of California, Berkeley (1970)

13.

Ogiwara, H., Kohno, T., Nakanishi, H., Nagayama, K., Sato, M., Yokota, J.: Unbalanced translocation, a major chromosome alteration causing loss of heterozygosity in human lung cancer. Oncogene 27, 4788–4797 (2008)CrossRef

14.

Oliver-Bonet, M., Navarro, J., Carrera, M., Egozcue, J., Benet, J.: Aneuploid and unbalanced sperm in two translocation carriers: evaluation of the genetic risk. Mol. Hum. Reprod. 8(10), 958–963 (2002)CrossRef

15.

Schöniger, M., Waterman, M.: A local algorithm for DNA sequence alignment with inversions. Bull. Math. Biol. 54, 521–536 (1992)CrossRef

16.

Vellozo, A.F., Alves, C.E.R., do Lago, A.P.: Alignment with non-overlapping inversions in O(n³)-time. In: Bücher, P., Moret, B.M.E. (eds.) WABI 2006. LNCS, vol. 4175, pp. 186–196. Springer, Heidelberg (2006). https://doi.org/10.1007/11851561_18CrossRef

17.

Warburton, D.: De novo balanced chromosome rearrangements and extra marker chromosomes identified at prenatal diagnosis: clinical significance and distribution of breakpoints. Am. J. Hum. Genet. 49, 995–1013 (1991)

18.

Weckselblatt, B., Hermetz, K.E., Rudd, M.K.: Unbalanced translocations arise from diverse mutational mechanisms including chromothripsis. Genome Res. 25(7), 937–947 (2015)CrossRef

Titel: Alignment of Sequences Allowing for Non-overlapping Unbalanced Translocations of Adjacent Factors
verfasst von: Simone Faro
Arianna Pavone
Verlag: Springer International Publishing
Buch: Bioinformatics and Biomedical Engineering
Print ISBN: 978-3-030-17937-3

Electronic ISBN: 978-3-030-17938-0

Copyright-Jahr: 2019
DOI: https://doi.org/10.1007/978-3-030-17938-0_12

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"