RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PERSONAL OFFICE
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Probl. Peredachi Inf.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Probl. Peredachi Inf., 2011, Volume 47, Issue 3, Pages 64–79 (Mi ppi2055)  

This article is cited in 6 scientific papers (total in 6 papers)

Large Systems

The tree nearest on average to a given set of trees

K. Yu. Gorbunov, V. A. Lyubetsky

Kharkevich Institute for Information Transmission Problems, Russian Academy of Sciences, Moscow

Abstract: We formulate the problem of constructing a tree which is the nearest on average to a given set of trees. The notion of “nearest” is formulated based on a conception of events such that counting their number makes it possible to distinguish each of the given trees from the desired one. These events are called divergence, duplication, loss, and transfer; other lists of events can also be considered. We propose an algorithm that solves this problem in cubic time with respect to the input data size. We prove correctness of the algorithm and a cubic estimate for its complexity.

Full text: PDF file (256 kB)
References: PDF file   HTML file

English version:
Problems of Information Transmission, 2011, 47:3, 274–288

Bibliographic databases:

Document Type: Article
UDC: 621.391.1+514
Received: 13.10.2010
Revised: 26.05.2011

Citation: K. Yu. Gorbunov, V. A. Lyubetsky, “The tree nearest on average to a given set of trees”, Probl. Peredachi Inf., 47:3 (2011), 64–79; Problems Inform. Transmission, 47:3 (2011), 274–288

Citation in format AMSBIB
\Bibitem{GorLyu11}
\by K.~Yu.~Gorbunov, V.~A.~Lyubetsky
\paper The tree nearest on average to a~given set of trees
\jour Probl. Peredachi Inf.
\yr 2011
\vol 47
\issue 3
\pages 64--79
\mathnet{http://mi.mathnet.ru/ppi2055}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2896177}
\transl
\jour Problems Inform. Transmission
\yr 2011
\vol 47
\issue 3
\pages 274--288
\crossref{https://doi.org/10.1134/S0032946011030069}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000299374700006}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84855917719}


Linking options:
  • http://mi.mathnet.ru/eng/ppi2055
  • http://mi.mathnet.ru/eng/ppi/v47/i3/p64

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. Gorbunov K.Y., Lyubetsky V.A., “Fast Algorithm to Reconstruct a Species Supertree From a Set of Protein Trees”, Mol. Biol., 46:1 (2012), 161–167  crossref  isi  elib  scopus
    2. Lyubetsky V.A., Rubanov L.I., Rusin L.Y., Gorbunov K.Yu., “Cubic Time Algorithms of Amalgamating Gene Trees and Building Evolutionary Scenarios”, Biol. Direct, 7 (2012), 48  crossref  isi  scopus
    3. Bolshoy A., Kirzhner V.M., “Algorithms of Ancestral Gene Length Reconstruction”, Biomed Res. Int., 2013, 472163  crossref  isi  elib  scopus
    4. A. V. Seliverstov, “Mnogogranniki i svyaznye podgrafy”, Diskretn. analiz i issled. oper., 21:3 (2014), 82–86  mathnet  mathscinet
    5. Strecht P., Mendes-Moreira J., Soares C., “Merging Decision Trees: a Case Study in Predicting Student Performance”, Advanced Data Mining and Applications, Adma 2014, Lecture Notes in Artificial Intelligence, 8933, eds. Luo X., Yu J., Li Z., Springer-Verlag Berlin, 2014, 535–548  isi
    6. Rusin L.Y., Lyubetskaya E.V., Gorbunov K.Y., Lyubetsky V.A., “Reconciliation of Gene and Species Trees”, Biomed Res. Int., 2014, 642089  crossref  isi  elib  scopus
  • Проблемы передачи информации Problems of Information Transmission
    Number of views:
    This page:147
    Full text:36
    References:24
    First page:5

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2018