IDEAS home Printed from https://ideas.repec.org/a/bpj/sagmbi/v16y2017i2p133-144n2.html
   My bibliography  Save this article

A time warping approach to multiple sequence alignment

Author

Listed:
  • Arribas-Gil Ana

    (Departamento de Estadística, Universidad Carlos III de Madrid, C/ Madrid, 126 - 28903 Getafe, Spain)

  • Matias Catherine

    (Sorbonne Universités, Université Pierre et Marie Curie, Université Paris Diderot, Centre National de la Recherche Scientifique, Laboratoire de Probabilités et Modèles Aléatoires, 4 place Jussieu, 75252 PARIS Cedex 05, France)

Abstract

We propose an approach for multiple sequence alignment (MSA) derived from the dynamic time warping viewpoint and recent techniques of curve synchronization developed in the context of functional data analysis. Starting from pairwise alignments of all the sequences (viewed as paths in a certain space), we construct a median path that represents the MSA we are looking for. We establish a proof of concept that our method could be an interesting ingredient to include into refined MSA techniques. We present a simple synthetic experiment as well as the study of a benchmark dataset, together with comparisons with 2 widely used MSA softwares.

Suggested Citation

  • Arribas-Gil Ana & Matias Catherine, 2017. "A time warping approach to multiple sequence alignment," Statistical Applications in Genetics and Molecular Biology, De Gruyter, vol. 16(2), pages 133-144, April.
    • Handle: RePEc:bpj:sagmbi:v:16:y:2017:i:2:p:133-144:n:2
    DOI: 10.1515/sagmb-2016-0043
    as

    Download full text from publisher

    File URL: https://doi.org/10.1515/sagmb-2016-0043
    Download Restriction: For access to full text, subscription to the journal or payment for the individual article is required.
    File URL: https://libkey.io/10.1515/sagmb-2016-0043?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Arribas-Gil, Ana & Müller, Hans-Georg, 2014. "Pairwise dynamic time warping for event data," Computational Statistics & Data Analysis, Elsevier, vol. 69(C), pages 255-268.
    2. Xueli Liu & Hans-Georg Muller, 2004. "Functional Convex Averaging and Synchronization for Time-Warped Random Curves," Journal of the American Statistical Association, American Statistical Association, vol. 99, pages 687-699, January.
    3. Cédric Notredame, 2007. "Recent Evolutions of Multiple Sequence Alignment Algorithms," PLOS Computational Biology, Public Library of Science, vol. 3(8), pages 1-4, August.
    4. Ana Arribas‐Gil & Elisabeth Gassiat & Catherine Matias, 2006. "Parameter Estimation in Pair‐hidden Markov Models," Scandinavian Journal of Statistics, Danish Society for Theoretical Statistics;Finnish Statistical Society;Norwegian Statistical Association;Swedish Statistical Association, vol. 33(4), pages 651-671, December.
    5. Arribas-Gil Ana, 2010. "Parameter Estimation in Multiple-Hidden I.I.D. Models from Biological Multiple Alignment," Statistical Applications in Genetics and Molecular Biology, De Gruyter, vol. 9(1), pages 1-37, January.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Irene Albarrán-Lozano & Pablo J. Alonso-González & Ana Arribas-Gil, 2017. "Dependence evolution in the Spanish disabled population: a functional data analysis approach," Journal of the Royal Statistical Society Series A, Royal Statistical Society, vol. 180(2), pages 657-677, February.
    2. Alonso González, Pablo, 2013. "Dependency evolution in Spanish disabled population : a functional data analysis approach," DES - Working Papers. Statistics and Econometrics. WS ws130403, Universidad Carlos III de Madrid. Departamento de Estadística.
    3. Mingfei Dong & Donatello Telesca & Catherine Sugar & Frederick Shic & Adam Naples & Scott P. Johnson & Beibin Li & Adham Atyabi & Minhang Xie & Sara J. Webb & Shafali Jeste & Susan Faja & April R. Lev, 2023. "A Functional Model for Studying Common Trends Across Trial Time in Eye Tracking Experiments," Statistics in Biosciences, Springer;International Chinese Statistical Association, vol. 15(1), pages 261-287, April.
    4. Rachdi, Mustapha & Laksaci, Ali & Demongeot, Jacques & Abdali, Abdel & Madani, Fethi, 2014. "Theoretical and practical aspects of the quadratic error in the local linear estimation of the conditional density for functional data," Computational Statistics & Data Analysis, Elsevier, vol. 73(C), pages 53-68.
    5. Arribas-Gil, Ana & Müller, Hans-Georg, 2014. "Pairwise dynamic time warping for event data," Computational Statistics & Data Analysis, Elsevier, vol. 69(C), pages 255-268.
    6. Aleksandra Rutkowska & Magdalena Szyszko, 2022. "New DTW Windows Type for Forward- and Backward-Lookingness Examination. Application for Inflation Expectation," Computational Economics, Springer;Society for Computational Economics, vol. 59(2), pages 701-718, February.
    7. Jason Cleveland & Wei Wu & Anuj Srivastava, 2016. "Norm-preserving constraint in the Fisher--Rao registration and its application in signal estimation," Journal of Nonparametric Statistics, Taylor & Francis Journals, vol. 28(2), pages 338-359, June.
    8. Alexander Kawrykow & Gary Roumanis & Alfred Kam & Daniel Kwak & Clarence Leung & Chu Wu & Eleyine Zarour & Phylo players & Luis Sarmenta & Mathieu Blanchette & Jérôme Waldispühl, 2012. "Phylo: A Citizen Science Approach for Improving Multiple Sequence Alignment," PLOS ONE, Public Library of Science, vol. 7(3), pages 1-9, March.
    9. Choros-Tomczyk, Barbara & Härdle, Wolfgang Karl & Okhrin, Ostap, 2013. "CDO surfaces dynamics," SFB 649 Discussion Papers 2013-032, Humboldt University Berlin, Collaborative Research Center 649: Economic Risk.
    10. Tucker, J. Derek & Wu, Wei & Srivastava, Anuj, 2013. "Generative models for functional data using phase and amplitude separation," Computational Statistics & Data Analysis, Elsevier, vol. 61(C), pages 50-66.
    11. Boudaoud, S. & Rix, H. & Meste, O., 2010. "Core Shape modelling of a set of curves," Computational Statistics & Data Analysis, Elsevier, vol. 54(2), pages 308-325, February.
    12. Arribas-Gil Ana & Matias Catherine, 2012. "A Context Dependent Pair Hidden Markov Model for Statistical Alignment," Statistical Applications in Genetics and Molecular Biology, De Gruyter, vol. 11(1), pages 1-29, January.
    13. Alonso González, Pablo J., 2017. "Estimating life expectancy free of dependency : group characterization through the proximity to the deepest dependency path," DES - Working Papers. Statistics and Econometrics. WS 24672, Universidad Carlos III de Madrid. Departamento de Estadística.
    14. Zhang, Zhen & Müller, Hans-Georg, 2011. "Functional density synchronization," Computational Statistics & Data Analysis, Elsevier, vol. 55(7), pages 2234-2249, July.
    15. Arribas-Gil Ana, 2010. "Parameter Estimation in Multiple-Hidden I.I.D. Models from Biological Multiple Alignment," Statistical Applications in Genetics and Molecular Biology, De Gruyter, vol. 9(1), pages 1-37, January.
    16. Cleveland, Jason & Zhao, Weilong & Wu, Wei, 2018. "Robust template estimation for functional data with phase variability using band depth," Computational Statistics & Data Analysis, Elsevier, vol. 125(C), pages 10-26.
    17. Ahn, Kyungmin & Tucker, J. Derek & Wu, Wei & Srivastava, Anuj, 2020. "Regression models using shapes of functions as predictors," Computational Statistics & Data Analysis, Elsevier, vol. 151(C).
    18. repec:hum:wpaper:sfb649dp2013-032 is not listed on IDEAS
    19. Juhyun Park & Jeongyoun Ahn, 2017. "Clustering multivariate functional data with phase variation," Biometrics, The International Biometric Society, vol. 73(1), pages 324-333, March.
    20. Choroś-Tomczyk, Barbara & Härdle, Wolfgang Karl & Okhrin, Ostap, 2016. "A semiparametric factor model for CDO surfaces dynamics," Journal of Multivariate Analysis, Elsevier, vol. 146(C), pages 151-163.
    21. Gerda Claeskens & Bernard W. Silverman & Leen Slaets, 2010. "A multiresolution approach to time warping achieved by a Bayesian prior–posterior transfer fitting strategy," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 72(5), pages 673-694, November.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:bpj:sagmbi:v:16:y:2017:i:2:p:133-144:n:2. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Peter Golla (email available below). General contact details of provider: https://www.degruyter.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.