-
Notifications
You must be signed in to change notification settings - Fork 3
/
Copy pathUpdates_and_News.txt
149 lines (117 loc) · 17.1 KB
/
Updates_and_News.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
23.06.2019:
- Доработаны функции семейства FindIn,
- Доработаны функции PairVectorCout, PairVectorFout.
- Добавлено семейство функций GraphCout и GraphFout: теперь можно выводить графы пореберно: каждое ребро в отдельной строке.
- Добавлена функция StrToCircular для нахождения кратчайшей "круговой" ("скрученной в кольцо") строки для заданной.
- Добавлено семество функций MaxFlowGraph для поиска максимального потока в графе, минимального разреза и нахождения одного из вариантов "сети путей", обеспечивающих максимальный поток.
- Для обеспечения более быстрого доступа к значению веса ребра в графе добавлена структура данных хранения графов - Ассоциативный массив смежности как вариант ранее предложенной и реализованной структуры Вектор смежности.
- Добавлены функции конвертации Вектора смежности в Ассоциативный массив смежности и назад. Важно: при конвертировании Векстора смежности в Ассоциативный массив смежности множественные ребра объединяются с суммированием весов.
- Добавлена TandemRepeatsFinding для поиска тандемных повторов в заданной строке, что может быть полезно в решениях задач в области Microsatellite Instability.
- Group of function "FindIn" has been updated.
- Functions PairVectorCout, PairVectorFout has been updated.
- Group of function "GraphCout" and "GraphFout" has been added. So nowadays one may "cout/ fout" a graph that is set by Adjacency vector to screen/ to file line by line: one edge in one line.
- Function "StrToCircular" added for finding the circular string of minimal length of the given one.
- Group of function MaxFlowGraph" has been added to help find Maximal Flow, the paths of the maximal flow network and max-flow min-cut in a graph.
- A data structure "Adjacency map" (a modification of data structure for containing graphs "Adjacency vector") has been added. Adjacency map allows to have quicker access to edge’s weight, but it can’t work with multiple edges.
- Functions for converting Adjacency vector to Adjacency map and conversely AdjVectorToAdjMap and AdjMapToAdjVector have been added. Note that Multiple edges will be joined together.
- Function TandemRepeatsFinding has been added. It is intended for finding tandem repeats in the given string that may be useful for solving problems related to Microsatellite Instability etc.
14.07.2019:
- Добавлена функция CIGAR1: Формирует строку CIGAR по результату "прикладывания" одной строки к другой с заданной позиции.
- Расширено семейство функций GraphCout и GraphFout: теперь можно выводить и графы, заданные ассоциативным массивом смежности.
- Добавлена функция EditDistA как расширенная версия функции EditDist: помимо редакционного расстояния возвращает также и один из возможных вариантов выравнивания строк.
- Function CIGAR1 has been added.
- Group of function "GraphCout" and "GraphFout" has been updated (so nowadays one may "cout/ fout" a graph that is set by both Adjacency vector and Adjacency map to screen/ to file line by line: one edge in one line).
- Function EditDistA as an extended version of the function EditDist has been added (returns not only the value of Edit Distance between 2 strings but also one possible version of the alignment itself).
09.08.2019
- Добавлено семейство функций NBPaths для поиска максимально длинных неразветвляющихся путей в графе (взвешенном, невзвешенном, ориентированном, неориентированном).
- Добавлены функции ConsStringQ1 и ConsStringQ2 для определения консенсусной строки с учетом качества символов в строках исходной коллекции. Ввиду малого объема данных для тестирования могут быть ошибки.
- Group of function "NBPaths" (for finding maximal non-branching paths in a graph, both weighted or no, direcyed or no) has been added.
- Functions ConsStringQ1 and ConsStringQ2 for building consensus string upon a given collection of strings according to their quality has been added. Note that due to little data for testing errors may be found here (please notify if you found any).
31.08.2019
- Добавлена функция GenRandomUWGraph для генерации случайного невзвешенного графа в виде вектора смежности.
- Добавлено семейство функций для нахождения областей связности неориентированного графа и областей сильной связности для ориентированного.
- Добавлено семейство функций для подсчета кратности ребер графов, заданных вектором смежности.
- Function GenRandomUWGraph that generates a random unweighted graph (as its "Adjacency vector") has been added.
- Group of function intended to find collection of vertices for each strongly connected component of directed graph and to find collection of vertices for each connected component of undirected graph has been added.
- Group of function for counting edges multiplicity of a graph that is set by Adjacency vector has been added.
19.10.2019
- Добавлены функции перекодирования Вектора смежности в/ из расширенного Ассоциативного массива смежности (AdjVectorToAdjMegaMap, AdjMegaMapToAdjVector) и расширено семейство функций вывода в файл и на экран графов, заданных расширенным Ассоциативным массивом смежности (GraphCout, GraphFout).
- Added group of functions AdjVectorToAdjMegaMap, AdjMegaMapToAdjVector to convert Adjacency vector to/ from Adjacency mega-map (i.e. extended version of Adjacency map to contain graphs having different multiply edges).
- Updated Group of function GraphCout and GraphFout to deal with mega-maps.
03.11.2019
- Семейство функций Num расширено.
- Добавлена функция ScoreStringMatrix для подсчета суммарного количества всех несовпадений символов по каждой позиции по набору строк.
- Добавлена функция GPPM (генерирует позиционную матрицу вероятностей; при этом может использоваться сглаживание (т. наз. "pseudocounts"): применена формула (Ns+z)/(N+2*z)).
- Group of functions Num updated.
- Function ScoreStringMatrix that counts score (i.e. total number of mismatches) upon vector a of strings s added.
- Function GPPM that generates a position probability matrix (PPM) added. Note that pseudocounts may be used (the formula (Ns+z)/(N+2*z) is implemented).
26.11.2019
- В функциях подбора консенсусных строк (в т.ч. - с учетом качества) ConsStringQ1 и ConsStringQ2 метод по умолчанию задан = 1.
- Добавлена функция JoinOverlapStrings - объединяет пересекающиеся строки (как с учетом качества, так и без (напр., коллекция коллекция вида 0->ACGT, 1->TGTA, 1->TT, 10->TT, 11->TCA без учета качества объединится как 0->ATGTA, 10->TTC)).
- Добавлена функция ProfileProbableMer - для поиска всех наиболее вероятных j-меров в строке исходя из заднанной позиционной матрицы вероятностей.
- Добавлена функция CycleToPath.
- For the functions ConsStringQ1 and ConsStringQ2 (intended for finding consesus string, in doing so quality may be taken into consideration or no) the default method is set = 1.
- Function JoinOverlapStrings for joining overlapping strings has been added (in doing so quality may be taken into consideration or no). So if we need to join collection 0->ACGT, 1->TGTA, 1->TT, 10->TT, 11->TCA in any way without any additional info,we should set NoQuality = true, Aggregate = false, and have the result: 0->ATGTA, 10->TTC.
- Function ProfileProbableMer to find all most probable j-mers in a given string upon a given position probability matrix (PPM) has been added.
- Function CycleToPath has been added.
11.01.2020
- Добавлены функции UPGMA_UndirectedGraph и NeighborJoiningUndirectedGraph для восстановления деревьев (в виде неориентированного графа) по матрицам дистанций методами присоединения ближайшего соседа и UPGMA.
- Added group of functions UPGMA_UndirectedGraph and NeighborJoiningUndirectedGraph for tree generating (as undirected graph) upon given distance matrix.
05.03.2020
- Добавлены экспериментальные функции для поиска всех циклов в графе () и всех путей между заданными вершинами в орграфе (AllPathsDGraph).
- Added experimental functions for finding all cycles in a graph (Circles_in_Graph) and all find all paths between any two vertices in a directed graph (AllPathsDGraph).
06.03.2020
- Добавлена функция SubGraphsInscribed для решения частного случая задачи поиска в некотором графе A всех подграфов, изоморфных заданному графу B (а именно, для поиска только «вписанных» подграфов), а также для проверки изоморфности двух графов.
- Added function SubGraphsInscribed to solve the particular case of the problem of finding in a some graph A all subgraphs that are isomorphic to given graph B (can be found “inscribed” subgraphs only); The function may be also used to check if 2 graphs are isomorphic.
This function can work with:
directed or undirected graphs,
graphs that have more than one connected components/ strongly connected components,
graphs that contain multiple edges.
"Inscribed" means here that (1) this subgraph is "glued" to other parts of A only by edges that connected to its vertices that are begin/ end ones of any max-length non-branching path of this subgraph and/ or (2) graph A may have some other connected components.
I.e. for graph B = {0->2, 10->2, 2->3, 3->4, 4->5, 4->6} we will find only A1 = {0->2, 1->2, 2->3, 3->4, 4->5, 4->6} as inscribed isomorphic subgraph of A = {0->2, 7->1, 1->2, 2->3, 3->4, 4->5, 4->6}.
But if we add edge 3->8 to A (in this case A = {3->8, 0->2, 7->1, 1->2, 2->3, 3->4, 4->5, 4->6}), we couldn't find any inscribed isomorphic to B subgraph of A.
29.03.2020
- Добавлены функции поиска медианных строк MedianString и генерации алфавита исходя из заданного набора строк GenerateAlphabet.
- Added functions MedianString and GenerateAlphabet.
22.04.2020
- Добавлена функция генерации алфавита исходя из одной заданной строки GenerateAlphabet.
- Добавлено семейство функций MakeSubgraphSetOfVertices для взятия подграфа из графа, заданного вектором смежности, по заданному набору вершин.
- Modified function GenerateAlphabet for a single string.
- Added group of function MakeSubgraphSetOfVertices to generate a subgraphs of a given graph (set by Adjacency vector) and a set/ unordered_set of vertices to be chosen.
04.05.2020
- Добавлена функция GraphVerticesNumbersCompress.
- Function GraphVerticesNumbersCompress has been added.
10.07.2020
- Добавлены функции для формирования суффиксного дерева по строке (SuffixTreeMake) и вывода суффиксного дерева в файл и на экран (CoutSuffixTree, FoutSuffixTree).
- Function SuffixTreeMake (to make a suffix tree upon a string) and CoutSuffixTree & FoutSuffixTree (to out suffix tree to screen or to file) has been added.
Suffix Tree will be contained in the vector of integers Tree, every edge as quartet of integers:
number of the start-vertex of edge, number of end-vertex of edge, starting position of substring of the basic string, the length of this substring.
04.09.2020
- Добавлены некоторые вспомогательные функции (MatrixEraseElement, UWGraphFromWGraph, WGraphFromUWGraph, PathFromPrev).
- Some auxiliary functions have been added (MatrixEraseElement, UWGraphFromWGraph, WGraphFromUWGraph, PathFromPrev).
05.12.2020
- Добавлен расширенный экспериментальный вариант функции SubGraphsInscribed, позволяющий находить все подграфы графа A, изоморфные графу B, а не только "вписанные".
Для этого нужно задать параметр InscribedOnly = 0. Если InscribedOnly == 1, то поиск идет быстрее, но только по "вписанным" подграфам.
Адаптация осуществлена заменой рассмотрения non-branching paths на ребра рассматриваемых графов с сохранением методологии.
- The extended experimental version of the function SubGraphsInscribed have been added.
This extention/ modifacation is done by working with all edges of the input graphs instead of working with non-branching paths.
If InscribedOnly == false the function finds all (not only inscribed) subgraphs of unweighted graph A that are isomorphic to unweighted graph B.
If InscribedOnly == true the function looks for "inscribed" ones only.
12.01.2021
- Добавлена функция SubGraphsInscribedM - экспериментальная версия функции SubGraphsInscribed. С ее помощью можно искать подграфы в графе по заданному образцу с учетом меток вершин (например, обозначения атомов для поиска по химическим формулам)
- Function SubGraphsInscribedM - i.e. an experimental version of the function SubGraphsInscribed - has been added.
SubGraphsInscribedM can find subgraphs in a given A that are isomorphic to a given template graph B too, but new is that vertices of these graphs may have marks. It may be useful for chemistry as one may associate an atom to some vertex (in case a molecule is set by graph).
13.01.2021
- Folder HowTo (contains some tutorial) has been added.
- Добавлен каталог HowTo (обучающие примеры использования нсекольких функций + исходные данные).
16.06.2021
- Functions VectorCout и MatrixCout are expanded to work with different containers (not only with vector) of standart type elements.
- Group of functions DistanceTS is expanded.
- Обобщено семейтсво функций VectorCout и MatrixCout - теперь работают с различными итерируемыми контейнерами элементов стандартных типов.
- Расширено семейтсво DistanceTS - теперь можно вычислять расстояния без вычисления массива "предков" и получать результат не только в long double.
19.06.2021
- Функции UWGraphFromPrev, PrevFromGraph, DegreesVerticesOfGraph добавлены.
- Функции UWGraphFromPrev, PrevFromGraph, DegreesVerticesOfGraph have been added.
27.06.2021
- Новые функции добавлены.
- Some functions have been added.